#include<cstdio>
#include<list>
#include<queue>
#define inf 10000000
#define NMAX 50005
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
LI a[NMAX],c[NMAX];
long n,m,d[NMAX],v[NMAX];
queue<long> q;
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()
{IT it,p;
 long k;
 for(k=2;k<=n;++k)
	 d[k]=inf;
 q.push(1);
  while(!q.empty())
  {k=q.front();
   v[k]=0;
    for(it=a[k].begin(),p=c[k].begin();it!=a[k].end();++it,++p)
     if(d[*it]>d[k]+*p)
		{d[*it]=d[k]+*p;
	     if(v[*it]==0)
		 {q.push(*it);
		  v[*it]=1;
		 }
		}
   q.pop();		
  }
}
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;
}