// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#define oo 2000000000
#define NOMINMAX
#include <windows.h>
#include <algorithm>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector<pair<int, int>> *edges;
bool *used;
int *dist;
int n, m;

void read() {
	f >> n >> m;
	edges = new vector<pair<int, int>>[n + 1];
	dist = new int[n + 1];
	used = new bool[n + 1];
	for (int i = 0; i < m; i++) {
		int a, b, cost;
		f >> a >> b >> cost;
		edges[a].push_back(make_pair(b, cost));
		edges[b].push_back(make_pair(a, cost));
	}
}

void write() {
	for (int i = 1; i <= n; i++) {
		g << dist[i] << " ";
	}
}

void dijsktra() {
	for (int i = 1; i <= n; i++) {
		used[i] = 0;
		dist[i] = oo;
	}
	dist[1] = 0;
	for (int i = 1; i <= n; i++) {
		int m = oo;
		int nod;
		for (int j = 1; j <= n; j++)
			if (!used[j] && dist[j] < m) {
				m = dist[j];
				nod = j;
			}
		used[nod] = 1;
		for (int j = 0; j < edges[nod].size(); j++) {
			int vecin = edges[nod][j].first, cost = edges[nod][j].second;
			dist[vecin] = min(dist[vecin], dist[nod] + cost);
		}
	}
}

void bellman_ford() {

}

int main()
{
	read();
	dijsktra();
	write();
    return 0;
}