#include<fstream>
#include<vector>
#include<queue>

#define dmax 50002
#define inf 999999

using namespace std;

int n,m;
int d[dmax],uz[dmax];
bool inq[dmax];

vector< pair<int, int> > a[dmax];
queue<int> q;


void citire()
{
 int i,x,y,c;
	
 FILE *fin;
 fin=fopen("dijkstra.in","r");
 
 fscanf(fin,"%d %d",&n, &m);
 for (i=1; i<=m; i++)
	 {
	  fscanf(fin,"%d %d %d",&x, &y, &c);
	  a[x].push_back(make_pair(y,c));
	 }
	
 fclose(fin);
}


void solve()
{
 int i,elem;
 vector< pair<int, int> >::iterator it;
	
 q.push(1);
 inq[1]=1;
 
 for (i=2; i<=n; i++)
	 d[i]=inf;
  
 while (q.size())
	 {
	  elem=q.front();
	   
	  for (it = a[elem].begin(); it != a[elem].end(); it++)
			  if (d[it -> first] > d[elem] + it -> second)
				 {
				  d[it -> first] = d[elem] + it->second;
				  
				  if (inq[it -> first] == 0)
					  {
					   q.push(it -> first);
					   inq[it -> first]=1;
					  }
				 }
		
	  inq[elem]=0;
	  q.pop();
	 }
}


void afisare()
{
 int i;
	
 ofstream fout("dijkstra.out");
 
 for (i=2; i<=n; i++)
	 if (d[i]!=inf)
		 fout<<d[i]<<" "; else
		 fout<<"0 ";
	
 fout.close();
}


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