#include<fstream>
#include<iostream>
#include<vector>
#define _swap(a,b) a=(a+b)-(b=a)
#define numaru 50001
#define INF (1<<23)
#define INFILE "dijkstra.in"
#define OUTFILE "dijkstra.out"
#include<conio.h>
using namespace std;
vector < pair<int, int> > Graf[numaru];
int n,d[numaru][2],min_heap[numaru],dim;
bool marc[numaru];
int min_heapADD(int i)
{
    if(dim==0)
    {
        min_heap[1]=i;
        dim=1;
        return 1;
    }
    else
    {
        int j=++dim;
        min_heap[j]=i;
        while(j!=1 && d[min_heap[j]][0]<d[min_heap[j/2]][0])
        {
            _swap(min_heap[j],min_heap[j/2]);
            j/=2;
        }
        return j;
    }
}
void min_heapDELETEHEAD()
{
    if(dim<=1)return ;
    int i;
    _swap(min_heap[1],min_heap[dim]);
    --dim;
    for(i=1;i*2<=dim;)
    {
        i*=2;
        if(i+1<=dim && d[min_heap[i+1]][0]<d[min_heap[i]][0])++i;
        if(d[min_heap[i/2]][0]>d[min_heap[i]][0]) _swap(min_heap[i/2],min_heap[i]);
    }
}

int update_min_heap(int i)
{
    ///modificari asupra lui d[min_heap[i]][0] sau facut in dijkstra_in_action aici urc sau cobor valoarea in min_heap daca e cazul
    if(dim<=1)return i;
    int j=i*2;
    if(j+1<=dim && d[min_heap[j+1]][0]<d[min_heap[j]][0]) ++j;
    ///si mai mare decat minimul dintre fii sai sau e fruza
    if((i!=1 && d[min_heap[i/2]][0]<=d[min_heap[i]][0]) && ( i*2>dim || (j<=dim && d[min_heap[i]][0]<=d[min_heap[j]][0]))) return i;
    if(i!=1 && d[min_heap[i/2]][0]>d[min_heap[i]][0])
    {
        while(i!=1 && d[min_heap[i]][0]<d[min_heap[i/2]][0])
        {
            _swap(min_heap[i],min_heap[i/2]);
            i/=2;
        }
        return i;
    }
    else
    {
        for(;i*2<=dim;)
        {
            i*=2;
            if(i+1<=dim && d[min_heap[i+1]][0]<d[min_heap[i]][0])++i;
            if(d[min_heap[i/2]][0]>d[min_heap[i]][0]) _swap(min_heap[i/2],min_heap[i]);
        }
        return i;
    }
}

void afisminheap()
{
    for(int i=2,j=1;j<=dim;i*=2,cout<<"\n")
        for(;j<=dim && j<=i-1;cout<<d[min_heap[j]][0]<<" ",++j);
    cout<<"\n";
}

void citire()
{
    ifstream f(INFILE);
    int m,i,j,c;
    f>>n>>m;
    for(;m;--m)
    {
        f>>i>>j>>c;
        Graf[i].push_back(make_pair(j,c));
    }
    f.close();
}

void scrierez()
{
    ofstream g(OUTFILE);
    for(int i=2;i<=n;++i)
        if(d[i][0]==INF) g<<"0 ";
        else g<<d[i][0]<<" ";
    g.close();
}

void dijkstra_in_action()
{
    /// -1 nu a fost in heap
    /// -2 a fost in heap
    int _min,poz,marcate=0,i;
    for(i=1;i<=n;++i)
    {
        d[i][0]=INF;
        d[i][1]=-1;
    }
    for(i=0;i<Graf[1].size();++i)
    {
        d[Graf[1][i].first][0]=Graf[1][i].second;
        d[Graf[1][i].first][1]=min_heapADD(Graf[1][i].first);
    }
    d[1][0]=d[1][1]=0;
    marc[1]=true;
    while(marcate!=n && dim)
    {
        poz=min_heap[1];
        min_heapDELETEHEAD();
        d[poz][1]=-2;
        marc[poz]=true;
        ++marcate;
        for(i=0;i<Graf[poz].size();++i)
            if(d[Graf[poz][i].first][0]>d[poz][0]+Graf[poz][i].second)
            {
                d[Graf[poz][i].first][0]=d[poz][0]+Graf[poz][i].second;
                if(d[Graf[poz][i].first][1]==-1)
                {
                    d[Graf[poz][i].first][1]=min_heapADD(Graf[poz][i].first);
                }
                else if(d[Graf[poz][i].first][1]!=-2)
                {
                    d[Graf[poz][i].first][1]=update_min_heap(d[Graf[poz][i].first][1]);
                }
            }
    }
}

void testminheap()
{
    int temp[]={11,1,5,3,6,9,7,8,13,12,10,14},i,j;
    for(i=1;i<=temp[0];++i) {d[i][0]=temp[i];d[i][1]=min_heapADD(i);cout<<temp[i]<<" ";}cout<<"\n";
    afisminheap();
    cin>>i>>j;
    while(i!=0 && j!=0)
    {
        d[i][0]=j;
        d[i][1]=update_min_heap(d[i][1]);
        afisminheap();
        cout<<"\n";
        cin>>i>>j;
    }
}

int main()
{
    citire();
    dijkstra_in_action();
    //testminheap();
    scrierez();
    return 0;
}