#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

#define Nmax 50005
#define inf 1000000

vector<pair<int,int> >G[Nmax];
int n,m,d[Nmax];

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

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

void afisare()
{
	int i;
	
	ofstream g("dijkstra.out");
	for(i=2;i<=n;i++)
	  g<<(d[i]<inf?d[i]:0)<<" ";
      g.close();
}
int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
	
}