#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
 
constexpr int kMaxN = 50000;
constexpr int kMaxM = 250000;
constexpr int NIL = -1;
 
struct Edge {
    int v, weight;
    int next;
} G[kMaxM];
 
int head[kMaxN];
int dist[kMaxN];
bool in_stack[kMaxN];
 
bool df(const int node, const int depth_limit) {
	if (depth_limit == 0) {
		return false;
	}
	bool optimized_state = false;
    in_stack[node] = true;
    for (int i = head[node]; i != NIL; i = G[i].next) {
        const int adj_node = G[i].v;
        if (dist[adj_node] >= dist[node] + G[i].weight) {
        	optimized_state |= (dist[adj_node] > dist[node] + G[i].weight);
            dist[adj_node] = dist[node] + G[i].weight;
            if (not in_stack[adj_node]) {
                optimized_state |= df(adj_node, depth_limit - 1);
            }
        }
    }
    in_stack[node] = false;
    return optimized_state;
}
 
int main() {
	#ifdef INFOARENA
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    #endif
    int n, m; cin >> n >> m;
     
    memset(head, NIL, 4 * n);
    for (int i = 0; i < m; i += 1) {
        int u, v, weight; cin >> u >> v >> weight;
        G[i].v = v - 1;
        G[i].weight = weight;
        G[i].next = head[u - 1];
        head[u - 1] = i;
    }
     
    memset(dist + 1, 0x3f, 4 * (n - 1));
    
    int lo = 0, hi = (1 << 7);
    while (hi - lo > 1) {
    	int mid = (lo + hi) / 2;
    	if (df(0, mid)) {
    		lo = mid;
    	} else {
    		hi = mid;
    	}
    }
    
    for (int i = 1; i < n; i += 1) {
        cout << (dist[i] & -(dist[i] != 0x3f3f3f3f)) << " \n"[i == n - 1];
    }
    return 0;
}