#include<fstream>
#include<vector>
#include<iostream>
using namespace std;

#define MaxN 50001
#define inf 10000

vector <int> G[MaxN], C[MaxN];
int n, m, D[MaxN],S[MaxN];

void citire()
{
  int i, x, y, cost;
  
  ifstream f("dijkstra.in");
	f>>n>>m;
	
    for(i=1;i<=m;i++)
	{
	  f>>x>>y>>cost;
	  G[x].push_back(y);
	  C[x].push_back(cost);
	}

   f.close();
}

void initializare()
{
  int vecini,i;
  
  for(i=1;i<=n;i++)
	D[i]=inf;
  
  S[1]=1;
  D[1]=0;
  vecini=G[1].size();
  for(i=0;i<vecini;i++)
		D[G[1][i]]=C[1][i];
 
}

void dijkstra()
{
  int min, gasit,k,i,x,j;
  
	do{
		min=inf;
		gasit=0;
		for(i=1;i<=n;i++)
		  if(S[i]==0&&D[i]<min)
		  {
			min=D[i];
			k=i;
			gasit=1;
		  }
		S[k]=1;

		x=C[k].size();

		for(i=1;i<=n;i++)
		  for(j=0;j<x;j++)
			if(G[k][j]==i)
               if(D[i]>D[k]+C[k][j])
   				  D[i]=D[k]+C[k][j];
		  
	  }while(gasit);
}

void afisare()
{
  int i;
  ofstream g("dijkstra.out");
    
  for(i=2;i<=n;i++)
	g<<D[i]<<" ";
  g.close();
}

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