#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n,m,i,d[50005],x,g[50005],c;
struct nod{int nd,val;}p;
vector <nod>v[50005];
queue <int>C;
int main()
{freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%d%d",&n,&m);
 for(i=1;i<=m;i++)
    {scanf("%d%d%d",&x,&p.nd,&p.val);
     v[x].push_back(p);
     g[x]++;
    }
 C.push(1);
 for(i=1;i<=n;i++)
    d[i]=1000000000;
    d[1]=0;
 while(C.size()>0)
   {c=C.front();
    C.pop();
    for(i=0;i<g[c];i++)
       {if(v[c][i].val+d[c]<d[v[c][i].nd]){d[v[c][i].nd]=v[c][i].val+d[c];
                                           C.push(v[c][i].nd);
                                          }
       }
   }
for(i=2;i<=n;i++)
   {if(d[i]==1000000000)printf("0 ");
       else printf("%d ",d[i]);
   }
}