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

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int cost[50001];
int pct, edges;
queue<int> coada;
vector< pair <int, int> > muchii[50002];
struct Nod{
    int nod;
    int val;
};
Nod heap[500004];
int n;
Nod getMin()
{
    return heap[1];
}
void add(Nod x)
{

    n++;
    int poz=n;
    heap[n]=x;
    while(poz>1 && heap[poz/2].val>heap[poz].val)
    {
        swap(heap[poz/2], heap[poz]);
        poz/=2;
    }
}
int popMin()
{

    heap[1]=heap[n];
    heap[n]={0,0};
    int poz=1;
    n--;
    while(2*poz<=n)
    {
        poz*=2;
        if(poz<n && heap[poz].val>heap[poz+1].val) poz++;
        if(heap[poz].val < heap[poz/2].val)
            swap(heap[poz/2], heap[poz]);
        else poz=n;
    }
}


int main()
{
    f>>pct>>edges;
    for(int i=1;i<=edges;++i)
    {
        int c,b,a;
        f>>a>>b>>c;
        muchii[a].push_back(make_pair(b,c));

    }
     for(int i=1;i<=pct;++i)
       cost[i]=1e9;
    Nod nod={1,0};
    cost[1]=0;
    add({1,0});
    while(n>0)
    {
        nod=getMin();
        popMin();
        if(nod.val<=cost[nod.nod])
        {
            cost[nod.nod]=nod.val;
            for(int i=0; i<muchii[nod.nod].size(); ++i)
            {
                pair<int, int> copil=muchii[nod.nod].at(i);
                Nod cop;
                cop.nod=copil.first;
                cop.val=copil.second+cost[nod.nod];
                add(cop);
            }
        }
    }

    for(int i=2;i<=pct;++i)
    {
        if(cost[i]==1e9) g<<"0 ";
        else
         g<<cost[i]<<" ";
    }

    return 0;
}