#include <fstream>
#include <set>
#include <vector>
#define INF 2147483646
using namespace std;

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

vector< pair < int, int > > L[50005];
set< pair < int, int > > s;
int n, m, x, y, z, w[50005];
int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; i++){
        fin>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
    }
    for(int i = 2; i <= n; i++){
        w[i] = INF;
    }
    w[1] = 0;
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        int nod = s.begin() -> second;
        s.erase(s.begin());
        for(int i = 0; i < L[nod].size(); i++){
            if(w[nod] + L[nod][i].second < w[L[nod][i].first]){

                s.erase(make_pair(w[L[nod][i].first], L[nod][i].first));

                w[L[nod][i].first] = w[nod] + L[nod][i].second;

                s.insert(make_pair(w[L[nod][i].first], L[nod][i].first));
            }
        }
    }
    for(int i = 2; i <= n; i++){
        if(w[i] != INF){
            fout<<w[i]<<" ";
        }
        else{
            fout<<0<<" ";
        }
    }
    return 0;
}