#include <bits/stdc++.h>

using namespace std;
const int MAX = 50005;
const int INF = 1e9;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector < pair < int , int > > G[MAX];
set < pair < int , int > > T;
int C[MAX],n;
inline void dijkstra()
{
    int cost , nod;
    for(int i = 2 ; i <= n; i++)
        C[i] = INF;
    T.insert({0,1});
    while(!T.empty()){
        cost = (*T.begin()).first;
        nod = (*T.begin()).second;
        T.erase(*T.begin());
        for(int i = 0 ;  i < G[nod].size(); i++){
            if(C[G[nod][i].second] > C[nod] + G[nod][i].first){
               C[G[nod][i].second] = C[nod] + G[nod][i].first;
               T.insert({C[G[nod][i].second],G[nod][i].second});
            }
        }
    }
}

int main()
{
    int m,x,y,c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        G[x].push_back({c,y});
    }
    dijkstra();
    for(int i = 2 ; i <= n; i ++){
        if(C[i] == INF)
            fout << 0 << " ";
        else
            fout << C[i] << " ";
    }
    return 0;
}