P1014

#include <bits/stdc++.h>

typedef std::pair<int, int> PII;
const int N = 2510, M = 10010 + N, LIM = 500000000;
int n, m;
int head[N], nxt[M], to[M], wt[M], idx;
int h[N];
int d[N][N];
bool outq[N];
std::priority_queue<PII, std::vector<PII >, std::greater<PII > > q;

int myABS(int x) {
    return (x >= 0) ? x : (-x);
}
void add(int u, int v, int w) {
    nxt[idx] = head[u];
    to[idx] = v;
    wt[idx] = w;
    head[u] = idx;
    ++ idx;
    return;
}
void bellmanford(int s) {
    memset(h, 0x3f, sizeof(h));
    h[n + 1] = 0;

    for (int i = 1; i < n; ++ i) {
        for (int j = 1; j <= n + 1; ++ j) {
            for (int k = head[j]; k != -1; k = nxt[k]) {
                int v = to[k], w = wt[k];
                h[v] = std::min(h[v], h[j] + w);
            }
        }
    }

    return;
}
void dijkstra(int s) {
    for (int i = 1; i <= n; ++ i) {
        outq[i] = false;
    }
    d[s][s] = 0;
    q.push(std::make_pair(d[s][s], s));

    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (outq[x]) {
            continue;
        }
        outq[x] = true;

        for (int i = head[x]; i != -1; i = nxt[i]) {
            int v = to[i], w = wt[i] + h[x] - h[v];
            if (d[s][v] > d[s][x] + w) {
                d[s][v] = d[s][x] + w;
                q.push(std::make_pair(d[s][v], v));
            }
        }
    }

    return;
}

int main(void) {
    memset(head, -1, sizeof(head));

    scanf("%d%d", &n, &m);
    for (int i = 1, inpu, inpv, inpw; i <= m; ++ i) {
        scanf("%d%d%d", &inpu, &inpv, &inpw);
        add(inpu, inpv, inpw);
    }
    for (int i = 1; i <= n; ++ i) {
        add(n + 1, i, 0);
    }
    bellmanford(n + 1);

    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; ++ i) {
        dijkstra(i);
    }
    for (int i = 1; i <= n; ++ i) {
        int res = 0;
        for (int j = 1; j <= n; ++ j) {
            d[i][j] -= h[i] - h[j];
            if (d[i][j] < LIM) {
                res xor_eq (j + myABS(d[i][j]));
            } else {
                res xor_eq j;
            }
        }
        printf("%d ", res);
    }


    return 0;
}