#include<fstream>
#include<iostream>
#define INF 1<<30
using namespace std;
int a[5000][5000],n,m,x,y,c,vis[5000],d[5000];
int main()
{
  ifstream f("dijkstra.in");
  ofstream g("dijkstra.out");
  
  f>>n>>m;
  
  for(int i=0;i<m;i++)
  {
	  f>>x>>y>>c;
	  a[x][y] = c;
  }
  
  for(int i=1;i<=n;i++)
	  d[i] = INF;

  
  d[1] = 0;
  int counter = n;
  
  
  while(counter)
  {
    int min = INF;
	int minI;
    for(int i=1;i<=n;i++)
      if(d[i] < min && !vis[i])
	  {
		min = d[i];
		minI = i;
	  }
    
	vis[minI] = 1;
	
	
	for(int i=1;i<=n;i++)
	{
	  if(a[minI][i] != 0)
	  {
		if(d[minI]+a[minI][i] < d[i])
			d[i] = d[minI]+a[minI][i];
	  }
	}  
    counter--;
  }

  for(int i=2;i<=n;i++)
	  if(d[i] == INF)
		  g<<"0"<<" ";
	  else
		  g<<d[i]<<" ";
}