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

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int nod,nod2,n,m,i,x,y,z,D[50001];
vector<pair<int,int> > a[50001];
vector<pair<int,int> >::iterator it;

struct cmp
{
	bool operator() (const int &a,const int &b)
	{
		return (D[a]>D[b]);
	}
};

priority_queue<int,vector<int>,cmp> Q;

void dijkstra()
{
	while (!Q.empty())
	{
		nod=Q.top();
		Q.pop();
		
		for (it=a[nod].begin();it!=a[nod].end();it++)
		{
			nod2=(*it).first;
			if (D[nod2]==-1 || D[nod]+(*it).second<D[nod2])
			{
				D[nod2]=D[nod]+(*it).second;
				Q.push(nod2);
			}
		}
	}
}

int main()
{
	in>>n>>m;
	
	for (i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
	
	memset(D,-1,sizeof(D));
	D[1]=0;
	
	Q.push(1);
	dijkstra();
	
	for (i=2;i<=n;i++) 
	{
		if (D[i]==-1) D[i]=0;
		out<<D[i]<<' ';
	}
}