#include<fstream>
#include<set>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int> >L[50003];
set<pair<int, int> >s;
int i,j,n,m,a,b,c,q;
int V[50003],D[50003];
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        L[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;i++){
        D[i]=500000000;
    }
    D[1]=0;
    s.insert(make_pair(0,1));
    while(s.empty()==0){
        q=s.begin()->second;
        s.erase(s.begin());
        for(i=0;i<L[q].size();i++)
            if(D[L[q][i].first]>D[q]+L[q][i].second){
                s.erase( make_pair(D[L[q][i].first],L[q][i].first));
                D[L[q][i].first]=D[q]+L[q][i].second;
                s.insert(make_pair(D[L[q][i].first],L[q][i].first));
            }
    }
    for(i=2;i<=n;i++){
        if(D[i]==500000000){
            fout<<"0"<<" ";
        }
        else{
            fout<<D[i]<<" ";
        }
    }
    return 0;
}