#include <bits/stdc++.h>
#define NMAX 50005
#define INF 0xf3f3f3
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m;
vector <vector< pair<int,int> > > G;
void citire(){
    f>>n>>m;
    G.resize(n+1);
    for(int i=1,x,y,ct;i<=m;i++){
        f>>x>>y>>ct;
        G[x].push_back(make_pair(y,ct));
    }
}
vector <int> cost(NMAX,INF);
inline void dijkstra(int s){
    set< pair<int,int> >h;
    h.insert(make_pair(0,s));
    while(!h.empty()){
        int ct = h.begin()->first;
        int nod = h.begin()->second;
        h.erase(h.begin());
        for(auto it:G[nod]){
            int tonode=it.first;
            int tocost=it.second;
            if(cost[tonode]>ct+tocost){
                if(cost[tonode]!=INF)
                    h.erase(make_pair(cost[tonode],tonode));
                cost[tonode]=ct+tocost;
                h.insert(make_pair(ct+tocost,tonode));
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(cost[i]==INF)cost[i]=0;
        g<<cost[i]<<" ";
    }
}
int main()
{
    citire();
    dijkstra(1);
    return 0;
}