#include <iostream>
#include <ctime>
#include <vector>
#include <queue>
using namespace std;

int N, M, i, x, y, z;
struct dij
{
	int nod, cost;
}ob;

struct asd
{
	int cost, nod;
	bool operator < (const asd& var) const
	{
		return cost > var.cost;
	}
}w;

vector<dij> v [ 50010 ];
priority_queue<asd> pq;
int cd[50010];

void read(void)
{
	FILE *f = fopen("dijkstra.in", "r");
	fscanf(f, "%d%d", &N, &M);
	for(i = 1; i <= M; ++i)
	{
		fscanf(f, "%d%d%d", &x, &y, &z);
		ob.nod = y;
		ob.cost = z;
		v[x].push_back(ob);
	}
	fclose(f);
}

void dijkstra(void)
{
	memset(cd, -1, sizeof(cd));
	w.cost = 0;
	w.nod = 1;
	pq.push(w);
	for(i = 1; i <= N; ++i)
	{
		asd el = pq.top();
		pq.pop();
		int sz = pq.size();
		if(cd[el.nod] == -1)
		{
			cd[el.nod] = el.cost;
			for(int j = 0; j < v[el.nod].size(); ++j)
			{
				int nod=el.nod, adiacNod=v[nod][j].nod;
				int cost = el.cost, adiacCost = v[nod][j].cost + cost;
				if(cd[adiacNod] == -1)
				{
					w.cost = adiacCost;
					w.nod = adiacNod;
					pq.push(w);
				}
			}
		}
	}
}
void print(void)
{
	FILE *g = fopen("dijkstra.out", "w");
	for(i = 2; i <= N; ++i)
		fprintf(g, "%d ", cd[i]);
	
	fclose(g);
}

int main(void)
{
	read();
	dijkstra();
	print();
	
	return 0;
}