#include <fstream>   
#define MaxN 50001   
#define MaxVal 60000000   
using namespace std;   
fstream FIN ("dijkstra.in", ios::in);   
fstream FOUT("dijkstra.out", ios::out);   
  
int n,m;   
bool viz[MaxN], mod;   
int d[MaxN],h[MaxN], poz[MaxN];   
  
struct vert {   
    int info, cost;   
    vert *next;   
} *L[MaxN];   
  
  
  
  
  
void add(int ex1, int ex2, int c){   
  
    vert *p = new vert;   
    p->info = ex2;   
    p->cost = c;   
    p->next = L[ex1];   
    L[ex1] = p;   
  
};   
  
void read(){   
  
    FIN>>n>>m;   
       
    int ex1,ex2,c;   
    for (int i = 1; i <= m; ++ i){   
        FIN>>ex1 >>ex2 >>c;   
        add(ex1,ex2,c);   
    }   
}   
  
void swap(int &x, int &y){   
    int aux;   
    aux = x;   
    x = y;   
    y = aux;   
};   
  
inline int father(int x){   
    return x/2;   
}   
inline int l_son(int x){   
    return 2*x;   
};   
inline int r_son(int x){   
    return 2*x + 1;   
};   
  
void down_heap(int x){   
    int y;   
    y = poz[x];   
    while (y > 1 && (d[ h[ father(y) ] ] > d[ h[y] ])){   
           
        swap(poz[ h[father(y)] ], poz[ h[y] ]);   
        swap(h[ father(y) ], h[y]);   
        y = father(y);  
    }   
};   
  
void up_heap(int x){   
    int fiu,y;   
    y = poz[x];   
    do{   
        fiu = 0;   
        if ( l_son(y) <= h[0]){   
            fiu = l_son(y);   
           
            if (r_son(y) <= h[0] && d[ h[ r_son(y) ] ] < d[ h[ l_son(y) ] ] )   
                fiu = r_son(y);   
            if ( d[ h[ fiu ] ] >= d[ h[ y ] ] )   
                fiu = 0;   
        }   
        if (fiu){   
            swap(poz[ h[y] ], poz[ h[fiu] ]);   
            swap(h[ y ], h[fiu]);
			y = fiu;
        }   
    }   
    while (fiu);       
       
};   
void dijkstra(){   
    int min, min_ind;   
    min_ind = 1;   
    h[0] = n;   
    for (int i = 2; i <= n; ++ i)   
        d[i] = MaxVal;   
    for (int i = 1; i <= n; ++ i)   
        h[i] = i, poz[i] = i;   
    do {   
       
    for (vert *p = L[min_ind]; p != NULL; p = p->next)   
        if (! viz[p->info])   
            if (d[min_ind] + p->cost < d[p->info])   
                d[p->info] = d[min_ind] + p->cost, down_heap(p->info);   
    viz[min_ind] = true;   
       
  
    h[1] = h[ h[0] ];    
    poz[h[1]] = 1;   
    --h[0];   
  
    if (h[0] != 0)up_heap(h[1]);   
    min_ind = h[1];   
    }while (h[0] != 0 && d[h[1]] != MaxVal);       
  
}   
  
void print(){   
  
    for (int i = 2; i <= n; i++)   
        if (d[i] == MaxVal) FOUT<<"0 ";   
        else FOUT<<d[i]<<" ";   
}   
  
int main(){   
  
    read();   
    dijkstra();   
    print();   
  
return 0;   
};