#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,x,y,c,q,cost,vecin,nod,nod1;
int d[50005];
vector <pair <int, int> > v[50005];
priority_queue< pair<int, int>,vector<pair<int, int> >,greater<pair<int, int> > > Heap;
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(i=2;i<=n;i++){
        d[i]=2000000000;
    }
    Heap.push(make_pair(0,1));
    while(!Heap.empty()){
        nod=Heap.top().second;
        nod1=Heap.top().first;
        Heap.pop();
        if(d[nod]>nod1){
            for(vector <pair <int,int > > :: iterator it=v[nod].begin();it!=v[nod].end();it++){
                vecin=it->first;
                cost=it->second;
                if(d[vecin]>d[nod]+cost){
                    d[vecin]=d[nod]+cost;
                    Heap.push(make_pair(d[vecin],vecin));
                }
            }
        }
    }
    for(i=2;i<=n;i++){
        if(d[i]!=2000000000){
            fout<<d[i]<<" ";
        }
        else{
            fout<<"0"<<" ";
        }
    }
    return 0;
}