#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 long long INF = INT_MAX;

struct NodeCost
{
    int node;
    long long cost;
};

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

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

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

    for(long long 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++)
    {
        fout << dist[i] << ' ';
    }

    return 0;
}

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

    priority_queue<NodeCost, vector<NodeCost>, cmpNodeCost> next;
    int nodes = dist.size();
    long long 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]));
            }
        }
    }
}