#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define INF 9999999
#define nmax 50009
using namespace std;
struct Coord{
 int x,cost;
 bool operator <(const Coord& e) const
 {
     return cost<e.cost;
 }
};
struct nod{
 int a,c;
};
priority_queue<Coord>q;
int n,m,ok[nmax],dp[nmax];
vector<nod>G[nmax];
inline void Create(){
 for(int i = 1; i<=n;i++)
    dp[i]=INF;
}
inline void bfs(){
 int i,k,j;
 dp[1]=0;
 k=1;
 Coord w,b;
 w.x=1;
 w.cost=0;
 ok[1]=1;
 q.push(w);
 while(!q.empty()){
    w=q.top();
    ok[w.x]=0;
    q.pop();

    for(i = 0 ; i < G[w.x].size();i++){

      if(dp[G[w.x][i].a] > dp[w.x]+G[w.x][i].c){

         dp[G[w.x][i].a]=dp[w.x]+G[w.x][i].c;
         if(!ok[G[w.x][i].a]){
            ok[G[w.x][i].a]=1;
            b.x=G[w.x][i].a;
            b.cost=G[w.x][i].c;
            q.push(b);
         }
         }
    }
 }
}
inline void Afis(){
    for(int i = 2;i<=n;i++)
    {
        if(dp[i] == INF) dp[i]=0;
        cout << dp[i]<<' ';
    }
}
int main(){
    int x,y,cost;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&x,&y,&cost);
        nod w;
        w.a=y;
        w.c=cost;
        G[x].push_back(w);
    }
    Create();
    bfs();
    Afis();
    return 0;
}