#include <iostream>
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
#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;
    
    void operator=(NodeCost t);
    bool operator==(NodeCost t);
    bool operator<(const NodeCost t) const;
};

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

int main()
{
    int nodes, arcs;

    fin >> nodes >> arcs;
    vector<long long> dist(nodes, INF);
    vector<list<NodeCost>> neighbors(nodes);

    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++)
    {
        if(dist[i] == INF)
            dist[i] = 0;

        fout << dist[i] << ' ';
    }

    return 0;
}

void dijkstra(int start, vector<long long> &dist, vector<list<NodeCost>> &neighbors)
{
    priority_queue<pair<long long, long long>> next;
    long long node, tdist;

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

    while(!next.empty())
    {
        node = next.top().second;
        tdist = -next.top().first;
        next.pop();

        if(tdist > dist[node])
        {
            continue;
        }

        for(auto& e : neighbors[node])
        {
            if(tdist + e.cost < dist[e.node])
            {
                dist[e.node] = tdist + e.cost;
                next.push(make_pair(-dist[e.node], e.node));
            }
        }
    }
}
NodeCost makeNodeCost(int node, long long cost)
{
    NodeCost temp;
    temp.node = node;
    temp.cost = cost;
    return temp;
}
void NodeCost::operator=(NodeCost t)
{
    this->node = t.node;
    this->cost = t.cost;
}
bool NodeCost::operator==(NodeCost t)
{
    return this->cost == t.cost && this->node == t.node;
}
bool NodeCost::operator<(const NodeCost t) const
{
    return this->cost > t.cost;
}