ff

<code>import java.io.*;
import java.util.*;

public class SpectrumFinder {

    class Edge {
        int from, to;
        int c;
        Edge backEdge;
        int edgeNum;
        long[] dp;
        long[] dpPrev;

        public Edge(int from, int to, int c, int edgeNum, int M) {
            this.from = from;
            this.to = to;
            this.c = c;
            this.edgeNum = edgeNum;
            this.dp = new long[M];
            this.dpPrev = new long[M];
        }

        void dpNextStep() {
            long[] tmp = dp;
            dp = dpPrev;
            dpPrev = tmp;
            Arrays.fill(dp, 0);
        }
    }

    ArrayList<Edge>[] g;
    ArrayList<Edge> edges;

    void clearDp() {
        for (Edge e : edges) {
            Arrays.fill(e.dp, 0);
            Arrays.fill(e.dpPrev, 0);
        }
    }

    void dpNextStep() {
        for (Edge e : edges) {
            e.dpNextStep();
        }
    }

    void addBiEdge(int from, int to, int c, int M) {
        Edge e1 = new Edge(from, to, c, edges.size(), M);
        edges.add(e1);
        Edge e2 = new Edge(to, from, -c, edges.size(), M);
        edges.add(e2);

        e1.backEdge = e2;
        e2.backEdge = e1;
        g[from].add(e1);
        g[to].add(e2);
    }

    void solve(Scanner in, PrintWriter out) {
        // Input and init
        int n = in.nextInt(); // Count vertices
        int m = in.nextInt(); // Count edges
        int M = in.nextInt(); // Module of expansion
        int spectrumSize = in.nextInt();
        g = new ArrayList[n + 1];
        edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            if (from >= n || to >= n) {
                throw new AssertionError("edge indices out of range");
            }
            int c = in.nextInt();
            addBiEdge(from, to, c, M);
        }
        int fakeRoot = n;
        for (int i = 0; i < n; i++) {
            addBiEdge(fakeRoot, i, 0, M);
        }

        // Solve
        long[] spectrum = new long[spectrumSize + 1];
        for (int root = 0; root < n; root++) {
            clearDp();

            for (Edge e : g[fakeRoot]) {
                if (e.to == root) {
                    e.dp[0] = 1;
                }
            }

            for (int len = 1; len <= spectrumSize; len++) {
                dpNextStep();

                for (Edge e : edges) {
                    for (Edge e2 : g[e.from]) {
                        if (e2.edgeNum != e.edgeNum) {
                            Edge eIncoming = e2.backEdge;
                            int wNext = (e.c % M + M) % m;
                            for (int w = 0; w < M; w++, wNext++) {
                                if (wNext >= M) {
                                    wNext -= M;
                                }
                                e.dp[wNext] += eIncoming.dpPrev[w];
                            }
                        }
                    }
                }

                for (Edge e : g[root]) {
                    Edge incoming = e.backEdge;
                    spectrum[len] += incoming.dp[0];
                }
            }
        }

        // Output
        for (int i = 1; i <= spectrumSize; i++) {
            out.print(spectrum[i] + " ");
        }
        out.println();
    }

    void run() {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        solve(in, out);

        out.close();
    }

    public static void main(String[] args) {
        new SpectrumFinder().run();
    }

}

</code>