#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];
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()
{
  vector< pair<int, int> > ::iterator it;
	int nod,primul;
 queue<int>Q;
 bool viz[Nmax];
 
  memset(cost,inf,sizeof(cost));
  memset(viz,false, sizeof(viz));
 
  viz[1]=true;
  cost[1]=0;
  Q.push(1);
  
  while(!Q.empty())
  {
	nod=Q.front();
	Q.pop();
	viz[nod]=false;
	
  for(it=G[nod].begin();it!=G[nod].end();it++)
  {
	  primul=it->first;
	if(cost[nod]+it->second<cost[primul])
	{
		cost[primul]=cost[nod]+it->second;
	    if(!viz[primul])
	     {
	       Q.push(primul);
	       viz[primul]=true;
	     }
	}
    }
  }
}

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;
}