#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define pr pair<int,int>
#define NMAX 50001
#define INF (1<<30)
using namespace std;

// const int NMAX = 50001;
// const int INF = 20000;

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

struct Compare 
{
	bool operator() (const pr &a, const pr &b) const
	{	
		return a.second < b.second;
	}
};

priority_queue < pr, vector< pr >, Compare> Q;
vector < pr > Graf[NMAX];
int nr_nod;
int dist[NMAX];

void Read()
{
	int from,to,by,muchii;
	in >> nr_nod >> muchii;
	//dist = new int[nr_nod+1];
	//Graf = new vector<pr>[nr_nod+1];
	for (int i = 0; i < muchii; ++i)
	{
		in >> from >> to >> by;
		Graf[from].push_back(pr(to,by));
	}	
}
void Dijkstra(int sursa)
{
	int to,by,from;
	for (int i = 1; i < nr_nod+1; ++i)
		dist[i] = INF;
	dist[sursa] = 0;
	Q.push(pr(sursa,dist[sursa]));
	
	while (!Q.empty())
	{
		from = Q.top().first;
		Q.pop();
		int size = Graf[from].size();
		for (int i = 0; i < size; ++i)
		{
			//to = Graf[from][i].first;
			//by = Graf[from][i].second;
			//cout<<from<<" "<<to<<" "<<by<<"\n";
			if (dist[Graf[from][i].first] > dist[from] + Graf[from][i].second)
			{
				dist[Graf[from][i].first] = dist[from] + Graf[from][i].second;
				Q.push(pr(Graf[from][i].first,dist[Graf[from][i].first]));
			}
		}
	}
}
void Print()
{
	for (int i = 2; i < nr_nod+1; ++i)
		if(dist[i] == INF)
			out << "0 ";
		else
			out << dist[i] << " ";
}
int main(int argc, char const *argv[])
{
	Read();
	Dijkstra(1);
	Print();
	return 0;
}