#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define N 50001
#define I (1<<30)
#define PII pair<int,int>
int n,m,d[N],i,j,x,y,c,k;
vector<PII> h[N];
bool v[N];
queue<PII> q;
int main()
{
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>x>>y>>c,h[x].push_back(make_pair(y,c));
	for(i=2;i<=n;i++)
		d[i]=I;
	q.push(make_pair(1,0));
	while(!q.empty())
	{
		x=q.top().first,q.pop();
		if(!v[x])
			for(v[x]=1,k=h[x].size(),j=0;j<k;j++)
				if(d[h[x][j].first]>d[x]+h[x][j].second)
					d[h[x][j].first]=d[x]+h[x][j].second,q.push(make_pair(h[x][j].first,d[h[x][j].first]));
	}
	for(i=2;i<=n;i++)
		g<<(d[i]==I?0:d[i])<<' ';
}