#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
const int noduri=100001;
bool inq[noduri];
struct pereche{
	int cost,next;
};
queue<int> q;
vector<pereche> graf[noduri];
int n,dist[noduri];
void citire()
{
	int m,x,i;
	pereche aux;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>aux.next>>aux.cost;
		graf[x].push_back(aux);
	}
}
void dijkstra(int x0)
{
	int x,y;
	for(int i=1;i<=n;i++)
		dist[i]=-1;
	inq[x0]=true;
	q.push(x0);
	dist[x0]=0;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		inq[x]=false;
		for(size_t i=0;i<graf[x].size();i++)
		{
			y=graf[x][i].next;
			if(dist[y]>dist[x]+graf[x][i].cost || dist[y]==-1)
			{
				if(!inq[y])
				{
					q.push(y);
					inq[y]=true;
				}
				dist[y]=dist[x]+graf[x][i].cost;
			} 
		}
	}
}
int main()
{
	int i;
	citire();
	dijkstra(1);
	for(i=2;i<=n;i++)
		h<<dist[i]<<' ';
	return 0;
}