// Dijkstra
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <set>
using namespace std;

const int infi = 2000000000;
vector<vector<int> > A, B;
int N, M;

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


int Distance;
void Dijkstra(vector<vector<int> >& adjacency_matrix, int start, int finish, const int infinity_value)
{
    vector<vector<int> > output_matrix;
    vector<int> D(adjacency_matrix.size(), infinity_value); vector<short> aparitions(adjacency_matrix.size(), 0);

    while (output_matrix.size() > 0)
        output_matrix.pop_back();
    for (int i = 0; i < adjacency_matrix.size(); i++)
        output_matrix.push_back(vector<int> (adjacency_matrix.size(), infinity_value));

	set<pair<int, int> > S;
	while (S.size() > 0) S.erase(*S.begin());
	D[start] = 0;
	S.insert(make_pair(0, start));


	while (S.size() > 0)
	{
		int cost = (*S.begin()).first, node = (*S.begin()).second;
		S.erase(*S.begin());
		if (aparitions[node]) continue;
		aparitions[node] = 1;
        for (int i = 0; i < adjacency_matrix[node].size(); i++)
            if (D[i] > cost + adjacency_matrix[node][i])
                D[i] = cost + adjacency_matrix[node][i], S.insert(make_pair(cost + adjacency_matrix[node][i], i));
	}

	Distance = D[finish];
    for (int i = 2; i <= N; i++)
        if (D[i] != infinity_value) fout << D[i] << ' ';
        else fout << 0 << ' ';
/*
    int aux = finish;
	while (aux != start)
	{
        for (int i = 0; i < adjacency_matrix[aux].size(); i++)
            if (D[i] + adjacency_matrix[aux][i] == D[aux])
            {
                output_matrix[i][aux] = output_matrix[aux][i] = adjacency_matrix[aux][i], aux = i;
                break;
            }
	}*/

	//return output_matrix;
}

int main()
{
    fin >> N >> M;
    for (int i = 0; i <= N; i++)
        A.push_back(vector<int> (M + 1, infi));

    for (int i = 1; i <= M; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        A[x][y] = cost;
    }
    Dijkstra(A, 1, 5, infi);

   // cout << Distance;
}