#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;
struct nod
{
    int y, c;
};
const int NMax = 50005;
const int INF = (1<<30) + 1;
vector< nod > G[NMax];
int d[NMax];
int n,m;
struct comp
{
    bool operator()(const int &a, const int &b)
    {
        return (d[a] > d[b]);
    }
};



void Dijkstra(int source)
{
    int from,i;
    priority_queue<int, vector<int> , comp> Heap;
    for(i = 1 ; i <= n; i++) d[i] = INF;

    d[source] = 0 ;
    Heap.push(source);

    while(!Heap.empty())
    {
        from = Heap.top();
        Heap.pop();
        auto it = G[from].begin();
        for(; it != G[from].end(); it++)
        {
            if(d[it->y] > d[from] + it->c)
            {
                d[it->y] = d[from] + it->c;
                Heap.push(it->y);
            }
        }
    }

}

int main()
{
    int i;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    nod niu;
    int x,y,c;
    for(i = 1; i <= m; i++)
    {
        f>>x>>niu.y>>niu.c;
        G[x].push_back(niu);
    }
    Dijkstra(1);
    for(i = 2; i <= n ; i++)
    {
        if(d[i] == INF)
        {
         g<<0<<" ";
        }
        else
        {
            g<<d[i]<<" ";
        }
    }
}