#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 50005;
int extractMin(unordered_set<int> s, int* dMin, int N){
    int mini = INT_MAX;
    int poz = - 1;
    for(int i = 1; i <= N; ++i)
        if(s.find(i) == s.end() && dMin[i] < mini){
            mini = dMin[i];
            poz = i;
        }
    return poz;
}
int main()
{   int N, M;
    unordered_set<int> s;
    vector <pair<int, int>> adj[nmax];
    int dMin[nmax];
    fin >> N >> M;
    for(int k = 0; k < M; ++k){
        int i, j, cost;
        fin >> i >> j >> cost;
        adj[i].push_back(make_pair(j, cost));
    }

    dMin[1] = 0;
    for(int i = 2; i <= N; ++i)
        dMin[i] = 999999;
    int crt = extractMin(s, dMin, N);

    for(;crt != -1;){
        s.insert(crt);
        for(int i = 0; i < adj[crt].size(); ++i){
            if(dMin[crt] + adj[crt][i].second < dMin[adj[crt][i].first])
                dMin[adj[crt][i].first] = dMin[crt] + adj[crt][i].second;
        }

        crt = extractMin(s, dMin, N);
    }

    for(int i = 2; i <= N; ++i)
        if(dMin[i] != INT_MAX)
            fout << dMin[i] << ' ';
        else fout << 0 << ' ';

	return 0;
}