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

#include <fstream>
#include <vector>
#include <set>
#include <iostream>

#define DIM 50000;
#define INF DIM*1000;
using namespace std;

vector<std::pair<int, int>>adjacencylist[DIM];

set<std::pair<int, int>>tail;

int A, B, C, distances[DIM], N, M;

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


int main()
{
	f >> N >> M;

	for (int i = 0; i <= M - 1; i++)
	{
		f >> A >> B >> C;
		adjacencylist[A].push_back(std::make_pair(B, C));
	}
	for (int i = 0; i <= M - 1; i++)
	{
		distances[i] = INF;
	}
	distances[0] = 0;

	tail.insert(std::make_pair(0, 1))    // cost from 1 to 1 is 0 ;

		while (!tail.empty())    // cat timp setul nu este gol;
		{
			int vertex = tail.begin()->second;
			tauil.erase();

			for (int i = 0; i < adjacencylist[vertex].size(); i++)
			{
				int neighbour = adjacencylist[vertex][i].first;
				int cost = adjacencylist[vertex][i].second;
			}
			if ((distances[vertex] + cost) < distances[neighbour])
			{
				tail.erase(make_pair(distance[neighbour], neighbour));
				distances[neighbour] = distances[vertex] + cost;
				tail.insert(make_pair(distance[neighbour], neighbour));
			}


		}

	for (int i = 2; i <= M; i++)
	{
		if (distances[i] == INF)
		{
			g << "0";
		}
		else
		{
	       g << distances[i] << " ";
        }
	}

   
}