// Dijkstra
#include <iostream>
#include <fstream>
#include <vector>
#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;
vector<vector<int> > 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<bool> aparitions(adjacency_matrix.size(), false);

    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;
		// if (node == finish) break;
		aparitions[node] = true;
        for (int i = 0; i < adjacency_matrix[node].size(); i++)
            if (adjacency_matrix[node][i] != infinity_value)
                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++)
        fout << D[i] << ' ';
/*
    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] = A[y][x] = cost;
    }
    B = Dijkstra(A, 1, 5, infi);

    cout << Distance;
}