#include<fstream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=50005;
const int INF=1<<30;
int n,m;
typedef pair<int,int> edge;
vector<edge> G[MAXN];

class compare
{
	public:
	bool operator() (const int& a, const int& b)
	{
		return d[a]>d[b];
	}
};
priority_queue<int,vector<int>,compare> PQ;
void read()
{
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	int i,u,v,w;
	for (i=1; i<=n; ++i)
	{
		fin>>u>>v>>w;
		G[u].push_back(make_pair(v,w));
	}
	fin.close();
}
void write()
{
	ofstream fout("dijkstra.out");
	for (int i=2; i<=n; ++i)
	{
		if (d[i]==INF)
			fout<<"0 ";
		else
			fout<<d[i]<<' ';
	}
	fout.close();
}
void dijkstra(int src)
{
	for (int i=1; i<=n; d[i]=INF, ++i);
	d[src]=0;

	int u,v,w;
	PQ.push(src);
	while (!PQ.empty())
	{
		u=PQ.top();
		PQ.pop();
		for (vector<edge>::iterator it=G[u].begin(); it!=G[u].end(); ++it)
		{
			v=(*it).first;
			w=(*it).second;
			if (d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				PQ.push(v);
			}
		}
	}	
}
int main()
{
	read();
	dijkstra(1);
	solve();
	return 0;
}