#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#define INF 100000
#define Nmax 50001
using namespace std;

vector <pair<int,int> > adj[Nmax];
vector <int> dist(Nmax,INF);
queue <int> Q;
int n,m;

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

void Dijkstra(int root)
{dist[root]=0;
Q.push(root);
while (!Q.empty())
	{int nod=Q.front();
	Q.pop();
	for(unsigned int i=0;i<adj[nod].size();i++)
		if (dist[adj[nod][i].first]>dist[nod]+adj[nod][i].second)
			 {dist[adj[nod][i].first]=dist[nod]+adj[nod][i].second;
			  Q.push(adj[nod][i].first);}
	}
}

int main()
{
citire();
Dijkstra(1);
ofstream g("dijkstra.out");
for(int i=2;i<=n;i++)
	if (dist[i]==INF) g<<0<<" ";
		else g<<dist[i]<<" ";
return 0;
}