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

using namespace std;

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

struct heapNode{
    int dist, nod;
    inline bool operator < (const heapNode &other) const
    {
        return dist > other.dist;
    }
};

struct node {
    int cost, nod;
};

int nr_noduri, nr_muchii;
const int maxN=500005;
int dist[maxN];
priority_queue <heapNode> heap;
vector <node>  G[maxN];

void citire()
{
    fin>>nr_noduri>>nr_muchii;
    for(int i=1; i<=nr_noduri; i++)
    {
        int nod1;
        node nod2;
        fin>>nod1>>nod2.nod>>nod2.cost;
        G[nod1].push_back(nod2);
    }
}

void dijkstra()
{
    memset(dist, 0x3f3f3f, sizeof dist);
    heapNode nod1;
    nod1.dist=0;
    nod1.nod=1;
    heap.push(nod1);
    while(!heap.empty())
    {
        heapNode current=heap.top(), vecin;
        heap.pop();
        for(int i=0; i<G[current.nod].size(); i++)
        {
            vecin.nod=G[current.nod][i].nod;
            vecin.dist=current.dist + G[current.nod][i].cost;
            if(vecin.dist < dist[vecin.nod])
            {
                dist[vecin.nod]=vecin.dist;
                heap.push(vecin);
            }

        }
    }
}

int main()
{
    citire();
    dijkstra();
    for(int i=2; i<=nr_noduri; i++)
    {
        if(dist[i]==0x3f3f3f)
            fout<<0<<' ';
        else
            fout<<dist[i]<<' ';
    }
    return 0;
}