#include <fstream>	
#include <vector>
#include <set>
#define NMAX 50010
#define INF 1e9
using namespace std;
	
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int, int>> G[NMAX];

int main() 
{
	
    int n, m;	
    fin >> n >> m;
	
    for (int i = 0; i < m; ++i) 
    {
	
        int x, y, cost;
        fin >> x >> y >> cost;
        G[x].push_back(make_pair(y, cost));
	
    }
    vector<int>dist(n+2,INF);
    dist[1] = 0;
	
    set<pair<int, int>> d;
    d.insert(make_pair(0, 1));
	
    while (!d.empty()) 
    {
        int node = d.begin()->second;
        d.erase(d.begin());

        vector<pair<int, int>>::iterator i;
        for (i = G[node].begin(); i != G[node].end(); ++i) 
        {
            int node1 = i->first;
            int cost = i->second;
	
            if (dist[node1] > dist[node] + cost) 
            {
                if (dist[node1] != INF) 
                {
                    d.erase(d.find(make_pair(dist[node1], node1)));
                }
                dist[node1] = dist[node] + cost;
                d.insert(make_pair(dist[node1], node1));
            }
        }
    }
	
	
    for (int i = 2; i <= n; ++i) 
    {
        if (dist[i] == INF) 
        {
		   fout << 0 << " ";
        }
        else
        {
        	cout << dist[i] << " ";
        }
    }

    fin.close();
    fout.close();
	return 0;
	
}