#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <list>

using namespace std;

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

const int INF = INT_MAX;

struct NodeCost
{
    int node, cost;
};

NodeCost makeNodeCost(int node, int cost);
void dijkstra(int start, vector<int>& dist, vector<list<NodeCost>>& neighbors);

int main()
{
    int nodes, arcs;
    vector<list<NodeCost>> neighbors;
    vector<int> dist;

    fin >> nodes >> arcs;
    neighbors.resize(nodes);
    dist = vector<int>(nodes, INF);

    for(int i = 0, l, r, cost; i < arcs; i++)
    {
        fin >> l >> r >> cost;
        l--;
        r--;

        neighbors[l].push_back(makeNodeCost(r, cost));
    }

    dijkstra(0, dist, neighbors);

    for(int i = 1; i < dist.size(); i++)
    {   
        if(dist[i] == INT_MAX)
            fout << "0 ";
        else
            fout << dist[i] << ' ';
    }

    return 0;
}

NodeCost makeNodeCost(int node, int cost)
{
    NodeCost temp;
    temp.node = node;
    temp.cost = cost;
    return temp;
}
void dijkstra(int start, vector<int>& dist, vector<list<NodeCost>>& neighbors)
{
    struct cmpNodeCost
    {
        bool operator()(const NodeCost& a, const NodeCost& b)
        {
            return a.cost > b.cost;
        }
    };

    priority_queue<NodeCost, vector<NodeCost>, cmpNodeCost> next;
    int tdist, node;

    dist[0] = 0;
    next.push(makeNodeCost(0, 0));

    while(!next.empty())
    {
        node = next.top().node;
        tdist = next.top().cost;
        next.pop();

        if(tdist > dist[node])
            continue;
        
        for(auto& neighbor : neighbors[node])
        {
            if(tdist + neighbor.cost < dist[neighbor.node])
            {
                dist[neighbor.node] = tdist + neighbor.cost;
                next.push(makeNodeCost(neighbor.node, dist[neighbor.node]));
            }
        }
    }
}