#include <iostream>
#include <vector>



using namespace std;
#include <bits/stdc++.h>
void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D){
	
	stack<int> q;
	q.push(0);
	fill(D.begin(), D.end(), -1);
	D[0]=0;
	int s;
	while(q.size()!=0){
		s=q.top();
		q.pop();
		for(int i=0;i<M;i++){
			if(X[i]==s){
				q.push(Y[i]);
				if(D[Y[i]]>-1)D[Y[i]]=min(D[s]+P[i],D[Y[i]]);
				else D[Y[i]]=D[s]+P[i];
			}
		}
		
	}
}


int main() {
    int N, M;
    cin >> N >> M;

    vector<int> X(M), Y(M), P(M);
    vector<long long> D(N);

    for (int i = 0; i < M; i++) {
        cin >> X[i] >> Y[i] >> P[i];
    }

    mincammino(N, M, X, Y, P, D);

    for (int i = 0; i < N; i++) {
        cout << D[i] << ' ';
    }
    cout << '\n';
}