#include <bits/stdtr1c++.h>
#define INF 500010
#define maxn 500001
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <vector < pair <int, int> > > A;
int d[maxn], V[maxn];
int N, M, x0 = 1;

void addEdge(int x, int y, int c) {
    A[x].push_back(make_pair(y,c));
}

void init() {
    int x, y, c;
    fin >> N >> M;
    A.resize(N+1);
    for(int i=0; i < M; i++) {
        fin >> x >> y >> c;
        addEdge(x, y, c);
    }
    for(int i = 1; i <=N; i++) d[i] = INF;
    for(int j = 0; j < A[x0].size(); j++) {
        d[A[x0][j].first] = A[x0][j].second;
    }
    d[x0] = 0;
}

void dijkstra() {
    int dMin, VfMin;
    for(int j=1; j<N; j++) {
        dMin = INF;
        for(int i=1; i<=N; i++) {
            if(!V[i] && dMin > d[i]) {
                dMin = d[i];
                VfMin = i;
            }
        }
        V[VfMin] = 1;
        for(int i=1; i <=N; i++) {
            if(!V[i]){
                for(int k=0; k<A[VfMin].size(); k++) {
                    if(A[VfMin][k].first == i && d[i] > dMin + A[VfMin][k].second) {
                        d[i] = dMin + A[VfMin][k].second;
                        break;
                    }
                }
            }
        }

    }
}

int main()
{
    init();
    dijkstra();
    for(int i=2; i <= N; i++ ){
        if(d[i] == INF) d[i] = 0;
        fout << d[i] << " ";
    }
    return 0;
}