#include <iostream>
#include <fstream>
#include <vector>
#define oo 2000000000

using namespace std;

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

//int h[103][103];
vector <pair <int, int> > h[50003];
vector <pair <int, int> > hp;
vector <int> poz;
int t[50003],d[50003];
bool v[50003];

int pozfiumin(int n, int pozc)
{
    int poz1,poz2;
    poz1=2*pozc;
    poz2=poz1+1;
    if(poz2>n)
        return poz1;
    if(hp[poz1]<hp[poz2])
        return poz1;
    return poz2;
}

void depljos(int n, int pozc)
{
    if(pozc<=n/2)
    {
        int pozfmin=pozfiumin(n,pozc);
        if(hp[pozc]>hp[pozfmin])
        {
            //cout << pozc << ' ' << pozfmax << '\n';
            //cout << h[pozc].first << ' ' << h[pozc].second << ' ' << h[pozfmax].first << ' ' << h[pozfmax].second <<'\n';
            swap(hp[pozc],hp[pozfmin]);
            swap(poz[hp[pozc].second],poz[hp[pozfmin].second]);
            depljos(n,pozfmin);
        }
    }
}

void deplsus(int pozc)
{
    while(pozc>1 && hp[pozc/2]>hp[pozc])
    {
        swap(hp[pozc],hp[pozc/2]);
        swap(poz[hp[pozc].second],poz[hp[pozc/2].second]);
        pozc=pozc/2;
    }
}

int main()
{
    int n,m=0,i,j,c,cmin,p,k,x,l,dh;
    in >> n >> m;
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            h[i][j]=oo;
            if(i==j)
                h[i][j]=0;
        }
    }*/
    hp.resize(n+2);
    poz.resize(n+2);
    for(i=1;i<=n;i++)
    {
        hp[i]={oo,i};
        poz[i]=i;
    }
    for(i=n/2;i>=1;i--)
    {
        depljos(n,i);
    }
    dh=n;
    while(in >> i >> j >> c)
    {
        m++;
        //h[i][j]=c;
        h[i].push_back({j,c});
    }
    for(i=1;i<=n;i++)
    {
        d[i]=oo;
        t[i]=0;
        v[i]=0;
    }
    d[1]=0;
    for(i=0;i<n-1;i++)
    {
        p=hp[1].second;
        /*cmin=oo;
        for(j=1;j<=n;j++)
        {
            if(d[j]<cmin && !v[j])
            {
                cmin=d[j];
                p=j;
            }
        }*/
        //cout << cmin << ' ' << p << '\n';
        swap(hp[dh],hp[1]);
        swap(poz[hp[dh].second],poz[hp[1].second]);
        dh--;
        depljos(dh,1);
        l=h[p].size();
        //for(k=0;k<l;k++)
        /*{
            if(d[h[p][k].first]>d[p]+h[p][k].second)
            {
                d[h[p][k].first]=d[p]+h[p][k].second;
                t[h[p][k].first]=p;
            }
        }*/
        for(pair <int, int> k:h[p])
        {
            if(d[k.first]>d[p]+k.second)
            {
                d[k.first]=d[p]+k.second;
                t[k.first]=p;
                hp[poz[k.first]].first=d[k.first];
                deplsus(poz[k.first]);
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]<oo)
            out << d[i] << ' ';
        else
            out << 0 << ' ';
    }
}