#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

class adj
{
public:
    int node;
    int cost_to;

    adj(int node = 0, int cost_to = 0)
    {
        this->node = node;
        this->cost_to = cost_to;
    }

    friend bool operator>(const adj& a, const adj& b)
    {
        return a.cost_to > b.cost_to;
    }
};

int inf = 1000000001;

int n, start_node = 1;

vector<vector<adj>> adjs(50001);
int cost[50001];
bool seen[50001];

void dijkstra()
{
    int seen_ct = 0, cn_size = 0;

    for(int i = 1; i <= n; i++)
        cost[i] = inf;

    cost[start_node] = 0;

    priority_queue<adj, vector<adj>, greater<adj>> candidate_nodes;

    candidate_nodes.push(adj(start_node, 0));
    cn_size++;

    while(seen_ct < n)
    {
        adj valid;

        do
        {
            valid = candidate_nodes.top();
            candidate_nodes.pop();
            cn_size--;

            if(cn_size == -1)
                goto finish;
        }
        while(seen[valid.node]);

        seen_ct++;
        seen[valid.node] = true;

        for(const auto& elem : adjs[valid.node])
            if(!seen[elem.node]) 
                if(cost[valid.node] + elem.cost_to < cost[elem.node])
                {
                    cost[elem.node] = cost[valid.node] + elem.cost_to;
                    candidate_nodes.push(adj(elem.node, cost[elem.node]));
                    cn_size++;
                }
    }

    finish: return;
}

int main()
{
    int dummy;
    fin >> n >> dummy;

    int a, b, c;
    while(fin >> a >> b >> c)
    {
        adjs[a].push_back(adj(b, c));
    }

    dijkstra();

    for(int i = 2; i <= n; i++)
        fout << ((cost[i] == inf) ? 0 : cost[i]) << ' ';

    return 0;
}