#include <fstream>
#include <vector>
#include <queue>
using namespace std;


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

const int INF = 0x3f3f3f3f;

vector<vector<pair<int, int>>> G;
vector<int> d;
queue<int> Q;
int n, m;

void Read();
void Write();
void BFS(int x);

int main()
{
	Read();
	BFS(1);

	Write();
	is.close();
	os.close();
	return 0;
}

void Read()
{
	int i, j, cost;
	is >> n >> m;
	d = vector<int>(n+1, INF);
	d[1] = 0;
	G.resize(n + 1);
	for ( int t = 1; t <= m; ++t )
	{
		is >> i >> j >> cost;
		G[i].push_back(make_pair(j, cost));
	}
}

void Write()
{
	for(int i = 2; i <= n; ++i)
    {
        if(d[i] == INF)
            os << 0 << ' ';
        else
            os << d[i] << ' ';
    }
}

void BFS(int x)
{
	int k;
	d[x] = 0;
	Q.push(x);
	while ( !Q.empty() )
	{
		k = Q.front();
		Q.pop();
		for ( vector<pair<int, int>>::iterator it = G[k].begin(); it != G[k].end(); ++it )
		{
			if ( d[it->first] > d[k] + it->second )
			{
				d[it->first] = d[k] + it->second;
				Q.push(it->first);
			}
		}
	}
}