#include <fstream>
#include<vector>
#include<queue>
#include<string.h>
#define inf 999999
#define pp pair<int,int>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pp> a[50005];
int n,m,d[50001];
priority_queue<pp,vector<pp>, greater<pp> > q;
void cit(){
    int i,j,h,w;
    /*freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);*/
    fin>>n>>m;
    //scanf("%i%i",&n,&m);
    for(h=1;h<=m;h++){
        //scanf("%i%i%i",&i,&j,&w);
        fin>>i>>j>>w;
        a[i].push_back(pp(j,w));
    }
}
void dijkstra(){
    int i,k,x,y;
    pp p;
    for(i=1;i<=n;i++)
        d[i]=inf;
    q.push(make_pair(0,1));d[1]=0;
    while(!q.empty()){
        p=q.top();
        q.pop();
        k=p.second;
        if(d[k]!=p.first)
            continue;
        for(i=0;i<a[k].size();i++){
            x=a[k][i].first;
            y=a[k][i].second;
            if(d[x]>d[k]+y){
                d[x]=d[k]+y;
                q.push(make_pair(d[x],x));
            }
        }
    }
}
int main(){
    cit();
    dijkstra();
    for(int i=2;i<=n;i++)
        if(d[i]!=inf)
            //printf("%i",d[i]),printf(" ");
            fout<<d[i]<<" ";
        else
            fout<<0<<" ";
            //printf("0"),printf(" ");
    return 0;
}