#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

#define Nmax 50000
#define inf 10000

vector <pair<int,int> > G[Nmax];
int cost[Nmax], viz[Nmax];
int n;

void citire()
{
	int i, m, x,y,c;
	freopen("dijkstra.in","r",stdin);
	 scanf("%d%d",&n,&m);
	 
	 for(i=1;i<=m;i++)
	 {
		scanf("%d%d%d",&x,&y,&c);
		G[x].push_back(make_pair(y,c));
		
	 }
	 
	fclose(stdin);
}

void dijkstra()
{
 
	int nod;
 queue<int>Q;
 
  memset(cost,inf,sizeof(cost));
  
  viz[1]=1;
  cost[1]=0;
  Q.push(1);
  
  while(!Q.empty())
  {
	nod=Q.front();
	Q.pop();
	viz[nod]=0;
	
  for(vector< pair<int, int> > ::iterator it=G[nod].begin();it!=G[nod].end();it++)
	if(cost[nod]+it->second<cost[it->first])
	{
		cost[it->first]=cost[nod]+it->second;
	    if(!viz[it->first])
	     {
	       Q.push(it->first);
	       viz[it->first]=1;
	     }
	}
    }
  	
}

void afisare()
{
	int i;
	freopen("dijkstra.out","w",stdout);
     for(i=2;i<=n;i++)
        if(cost[i]<inf)
         printf("%d ",cost[i]);
        else		
		  printf("0 ");
	fclose(stdout);
}

int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}