#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define N 50001
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int b[N*5], c[N], l[N], r[N], n;
pair<int,int> a[N*5];
pair<int, int> h[N*5];
bool v[N];
void bfs(){
    int i,j,k=0,nr=0,cur;
    while(h[0].f!=-N*5){
        i=h[0].s;
        cur=-h[0].f;
        h[0].f=-N*5;
        pop_heap(h, h+k+1);
        if(!v[i]){
            v[i]=1;
            r[i]=cur;
            j=c[i];
            ++nr;
            while(j){
                if(!v[a[j].f]){
                    h[++k].f=-(r[i]+a[j].s);
                    h[k].s=a[j].f;
                    push_heap(h, h+k+1);
                }
                j=b[j];
            }

        }
    }
}
int main(){
    int m,i,x,y,z,k=0;
    in>>n>>m;
    for(i=1; i<=m; ++i){
        in>>x>>y>>z;
        a[++k].f=y;
        a[k].s=z;
        b[k]=c[x];
        c[x]=k;
    }
    h[0].s=1;
    bfs();
    for(i=2; i<=n; ++i)
		out<<r[i]<<" ";
    return 0;
}