#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;
vector <int> d; vector <int> V;
int N, M, x0 = 1;

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

void init() {
    int x, y, c;
    fin >> N >> M;
    A.resize(N+1);
    d.resize(N+1); V.resize(N+1);
    for(int i=1; i<=N; i++) {
        for(int j=0; j<=N; j++) {
            A[i].push_back(make_pair(j, INF));
        }
    }
    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 = 1; 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] && d[i] > dMin + A[VfMin][i].second) d[i] = dMin + A[VfMin][i].second;
        }

    }
}

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