//Code by Patcas Csaba
//Time complexity:
//Space complexity:
//Method:
//Working time: 17 minute

#include <vector>
#include <string> 
#include <set> 
#include <map> 
#include <queue> 
#include <bitset> 

#include <numeric> 
#include <algorithm> 

#include <cstdio>
#include <fstream>
#include <iostream> 
#include <sstream> 

#include <cctype>
#include <cmath> 
#include <ctime>
#include <cassert>

using namespace std;

#define in_file "dijkstra.in"
#define out_file "dijkstra.out"

#define VI vector <int>
#define VB vector <bool>
#define PII pair <int, int>

#define FORN(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define repeat do{ 
#define until(x) }while(!(x)); 

#define SZ size()
#define B begin() 
#define E end() 
#define X first
#define Y second
#define RS resize
#define PB push_back
#define MP make_pair
#define ALL(x) x.begin(),x.end()

#define inf 2000000000

ifstream fin(in_file);
ofstream fout(out_file);


struct Tedge
{
	int node, cost;
};

int n, m;
vector < vector<Tedge> > g;
VI dv;

void AddEdge(int node1, int node2, int c)
{
	Tedge aux;
	aux.cost = c;
	aux.node = node2;
	g[node1].PB(aux);
}

void Solve()
{
	set <PII> d;
	d.insert(MP(0,1));
	VB was(n + 1, false);
	was[1] = true;
	dv[1] = 0;
	FORN(i, n)
	{
		PII min = *d.B;
		int node = min.Y;
		was[node] = true;
		assert(d.find(MP(dv[node], node)) != d.end());
		d.erase(d.find(MP(dv[node], node)));
		FORN(j, g[node].SZ)
		{
			int aux = g[node][j].node;
			if (!was[aux] && dv[aux] > dv[node] + g[node][j].cost)
			{
				set <PII>::iterator it = d.find(MP(dv[aux], aux));
				if (it != d.E) d.erase(it);
				dv[aux] = dv[node] + g[node][j].cost;
				d.insert(MP(dv[aux], aux));
			}
		}
	}
}

int main()
{
	//Read data
	fin>>n>>m;
	g.RS(n + 1);
	dv.RS(n + 1, inf);
	FORN(i, m)
	{
		int x, y, z;
		fin >> x >> y >> z;
		AddEdge(x, y, z);
	}
	fin.close();

	//Solve
	Solve();

	//Write data
	FOR(i, 2, n) fout << dv[i] << " ";
	fout.close();

	return 0;
}