#include<cstdio>
#include<set>
#include<list>
#define NMAX 50005
#define mp make_pair
#define inf 10000000
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
multiset< pair<long,long> > s;
LI a[NMAX],c[NMAX];
long d[NMAX],n,m;
void cit()
{long i,x,y,cost;
  freopen("dijkstra.in","r",stdin);
   scanf("%ld%ld",&n,&m);
    for(i=1;i<=m;++i)
	{scanf("%ld%ld%ld",&x,&y,&cost);
	 a[x].push_back(y);
     c[x].push_back(cost);
	}
 fclose(stdin);
}
void solve()
{long x,i,j,v;
 IT it,p;
 multiset< pair<long,long> >::iterator q;
 for(i=2;i<=n;++i)
	 d[i]=inf;
	 s.insert(mp(0,1));
  for(;s.empty()==0;)
	{q=s.begin();x=(*q).second;v=(*q).first;
     s.erase(q);
	
	  for(it=a[x].begin(),p=c[x].begin();it!=a[x].end();++it,++p)
		  if(d[*it]>v+*p)
		   d[*it]=v+*p,s.insert(mp(d[*it],*it));
	}
}
int main()
{cit();
 solve();
  freopen("dijkstra.out","w",stdout);
 long i;
  for(i=2;i<=n;++i)
	  if(d[i]==inf)
		  printf("%ld ",0);
	  else
		  printf("%ld ",d[i]);
 fclose(stdout);	  
 return 0;
}