#include <stdio.h>
#include <utility>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 0x3f3f3f3f
using namespace std;
int i,j,m,n,a,b,c,d[NMAX],initial,nod;
bool viz[NMAX];
vector <pair<int,int> > T[NMAX];
vector <pair<int,int> >::iterator it;
queue <int> coada;;
void solve()
{
    coada.push(initial);
    viz[initial]=true;
    while(!coada.empty())
    {
        nod=coada.front();
        viz[nod]=false;
        coada.pop();
        for(it=T[nod].begin();it!=T[nod].end();it++)
               if(d[nod]+it->second<d[it->first])
               {
                   d[it->first]=d[nod]+it->second;
                   if(viz[it->first]==false)
                   {
                       coada.push(it->first);
                       viz[it->first]=true;
                   }
               }
    }
}
int main()
{
    freopen("djikstra.in","r",stdin);
    freopen("djikstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<n+1;i++)
      d[i]=INF;
    for(i=1;i<m+1;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        T[a].push_back(make_pair(b,c));
    }
      initial=1;
      d[initial]=0;
      solve();
    for(i=2;i<n+1;i++)
        if(d[i]!=INF) printf("%d ",d[i]);
               else printf("0 ");
return 0;
}