/// 100 de puncte!!!
#include<fstream>
#include<set>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,x,y,c,k,nod,cost;
int D[50100];
multiset<pair<int,int> >s;
multiset<pair<int,int> >::iterator it;
vector<pair<int,int> > L[50005];
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=n;i++)
        D[i]=2000000000;
    s.insert(make_pair(0,1));
    while(!s.empty()){
        k=s.begin()->second;
        s.erase(s.begin());
        for(int i=0;i<L[k].size();i++){
            int cost=L[k][i].second;
            int nod=L[k][i].first;
            if(D[k]+cost<D[nod]){
                s.erase({D[nod],nod});
                D[nod]=D[k]+cost;
                s.insert({D[nod],nod});
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(D[i]==2000000000)
            fout<<0<<" ";
        else
            fout<<D[i]<<" ";
    return 0;
}