// project.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#define dim 100001
#include <vector>
#include <queue>
#pragma warning(disable:4996)
typedef unsigned long long ull;
typedef  long long ll;
using namespace std;

ifstream fin("date.in");
ofstream fout("date.out");


int n, m;
int f[50001];
int heap[500001]; //min-heap
vector<pair<int, int>> g[50001];
int d[50001];
int nr = 0;
static int inf = (1 << 29);
int start;

void afisare()
{
	for (int i = 2; i <= n; i++)
	{
		if (d[i] != inf) fout << d[i] << ' ';
		else fout << -1 << ' ';
	}
}

bool exista_heap()
{
	return nr > 0;
}

void cernere(int x)
{
	int fiu = x * 2;
	if (fiu + 1 <= nr && heap[fiu + 1] < heap[fiu]) fiu++;
	if (fiu <= nr && heap[fiu] < heap[x]) {
			
		swap(heap[x], heap[fiu]);
		cernere(fiu);
	}
}

void pop()
{
	swap(heap[1], heap[nr]);
	nr--;
	cernere(1);
}

void promovare(int nod)
{
	int tata = nod / 2;
	if (tata && heap[tata] > heap[nod])
	{
		swap(heap[tata], heap[nod]);
		promovare(tata);
	}
}

void heap_add(int nod)
{
	nr++;
	heap[nr] = nod;
	promovare(nr);
}

void dijkstra(int nod)
{
	for (int i = 1; i <= n; i++) d[i] = inf;
	heap_add(nod);
	f[nod] = 1;
	d[nod] = 0;
	while (exista_heap())
	{
		int k = heap[1];
		pop();
		f[k] = 0;
		for (int i = 0; i < g[k].size(); i++)
		{
			int vecin = g[k][i].first;
			int cost = g[k][i].second;
			if (d[k] + cost < d[vecin])
			{
				d[vecin] = d[k] + cost;
				if (f[vecin] == 0) {
					heap_add(vecin);
					f[vecin] = 1;
				}
			}
		}
	}
}

void verificare_heap()
{
	int n;
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		int cer;
		fin >> cer;
		if (cer == 1) {
			int x;
			fin >> x;
			heap_add(x);
		}
		else {
			fout << heap[1] << '\n';
			pop();
		}
	}
}


void citire()
{
	fin >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		fin >> a >> b >> c;
		g[a].push_back(make_pair(b, c));
	}
}

int main()
{
	citire();
	dijkstra(1);
	afisare();
	//verificare_heap();
}