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

#define pr pair<int,int>
#define NMAX 50001
#define INF 17000
using namespace std;

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

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int dist[NMAX];

struct Compare 
{
	bool operator() (const int &a, const int &b) const
	{	
		return dist[a] < dist[b];
	}
};

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

void Read(void)
{
	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(sursa);
	
	while (!Q.empty())
	{
		from = Q.top();
		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[to] > dist[from] + by)
			{
				dist[to] = dist[from] + by;
				Q.push(to);
			}
		}
	}
}
void Print(void)
{
	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;
}