#include<algorithm>
using namespace std;

#define DIM 50001
#define INF 1000001

struct djk{
    int d,q;};
    
struct graf{
    int nod,cost;
    graf *urm;};

int n,m;
djk a[DIM];
graf *lst[DIM];

void add(int val,int a,int b){
    graf *p=new graf;
    
    p->nod=b;
    p->cost=val;
    p->urm=lst[a];
    lst[a]=p;}

void dijkstra(){
    int i,j,poz,min0;
    graf *p;
    
    for(i=2; i<=n; ++i)
        a[i].d=INF;
    poz=0;
    for(i=1; i<=n; ++i){
        min0=INF;
        for(j=1; j<=n; ++j)
            if(a[j].d<min0&&!a[j].q){
                min0=a[j].d;
                poz=j;}
        a[poz].q=1;
        for(p=lst[poz]; p; p=p->urm)
            if(a[poz].d+p->cost<a[p->nod].d)
                a[p->nod].d=a[poz].d+p->cost;}}

void solve(){
    int i,x,y,val;
    graf *p;
    
    scanf("%d%d",&n,&m);
    for(i=0; i<m; ++i){
        scanf("%d%d%d",&x,&y,&val);
        add(val,x,y);}
    dijkstra();
    for(i=2; i<=n; ++i)
        printf("%d ",a[i].d);}

int main(){
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    solve();
    return 0;}