#include <iostream>
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
#define inf INT_MAX -10
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector < pair<int, int> > M[50001];
priority_queue < pair<int, int> > Q;
int n,m, D[50001], S[50001],P[50001];
void Citire()
{f>>n>>m;
int i,x,y,d,j;

for(i=1;i<=m;i++)
   {f>>x>>y>>d;
       M[x].push_back( make_pair(y, d) );
   }
}
void Dijktra()
{ int Start=1,min,i,poz,j,k,c;
for(i=1;i<=n;i++)
    if(i!=Start)
    {D[i]=inf;
     S[i]=0;
     P[i]=0;
    }

   for(k=0;k<M[Start].size();k++)
   {
       j=M[Start][k].first;
       c=M[Start][k].second;
       D[j]=c;
       P[j]=Start;
       Q.push(make_pair(-c,j));
   }
D[Start]=0;
S[Start]=1;
 while(!(Q.empty()))
 { //min=INT_MAX;
     poz=Q.top().second;
     Q.pop();
   /*  for(j=1;j<=n;j++)
        if(S[j]==0&&D[j]<min)
        {min=D[j];
         poz=j;
        } */
    S[poz]=1;
 for(k=0;k<M[poz].size();k++)
    {j=M[poz][k].first;
    c=M[poz][k].second;
    if(S[j]==0&&D[j]>D[poz]+c)
        {D[j]=D[poz]+c;
         P[j]=poz;
         Q.push(make_pair(-D[j],j));
         }
    }
 }
 for(i=2;i<=n;i++)
    if(D[i]==inf)
      g<<0<<" ";
    else g<<D[i]<<" ";
}
int main()
{ Citire();

Dijktra();
f.close();
g.close();
    return 0;
}