#include <fstream>
#include <vector>
#include <list>
#define INF (1<<30)-1
#define nmax 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector < pair <int, int> > v[nmax];
vector <int> h;
int n,ph[nmax],d[nmax];

void sift(int nod)
{
    int son=nod,f1,f2;
    do
    {
        nod=son; f1=2*nod; f2=2*nod+1;
        if(f1<h.size() && d[h[son]]>d[h[f1]]) son=f1;
        if(f2<h.size() && d[h[son]]>d[h[f2]]) son=f2;

        ph[h[son]]=nod;
        ph[h[nod]]=son;
        swap(h[son],h[nod]);

    }while(nod!=son);
}

void percolate(int nod)
{
    while(d[h[nod/2]]>d[h[nod]])
    {
        ph[h[nod/2]]=nod;
        ph[h[nod]]=nod/2;
        swap(h[nod],h[nod/2]);
        nod=nod/2;
    }
}

void adaugare(int x)
{
    h.push_back(x);
    ph[x]=h.size()-1;
    percolate(ph[x]);
}

int main()
{
    f>>n;
    int m,i,j,x,y,c,nod;
    f>>m;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    h.push_back(0);
    h.push_back(1);
    for(i=2;i<=n;i++) d[i]=INF;
    ph[1]=1;
    d[1]=0;
    while(h.size()>1)
    {
        nod=h[1];
        for(i=0;i<v[nod].size();i++)
        {
            x=v[nod][i].first;
            y=v[nod][i].second;
            if(d[x]==INF)
            {
                d[x]=y+d[nod];
                adaugare(x);
            }
            else if(d[x]>d[nod]+y)
            {
                d[x]=d[nod]+y;
                percolate(ph[x]);
            }
        }
        h[1]=h[h.size()-1];
        ph[h[1]]=1;
        h.pop_back();
        sift(1);
    }

    for(i=2;i<=n;i++)
        if(d[i]==INF) g<<0<<' ';
        else g<<d[i]<<' ';
}