#include <bits/stdc++.h>
using namespace std;

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

const int INF=2000000000;

int n,m,sz;
int d[50001],h[50001],pos[50001];
vector<pair<int,int>> v[50001];

void swp(int i,int j)
{
    swap(h[i],h[j]);
    pos[h[i]]=i;
    pos[h[j]]=j;
}

void up(int i)
{
    while(i>1 && d[h[i]]<d[h[i/2]])
    {
        swp(i,i/2);
        i/=2;
    }
}

void down(int i)
{
    while(true)
    {
        int l=2*i,r=l+1,best=i;

        if(l<=sz && d[h[l]]<d[h[best]])
            best=l;

        if(r<=sz && d[h[r]]<d[h[best]])
            best=r;

        if(best==i)
            break;

        swp(i,best);
        i=best;
    }
}

void citire()
{
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
}

void rezolvare()
{
    for(int i=1; i<=n; i++)
        d[i]=INF;

    d[1]=0;
    h[1]=1;
    pos[1]=1;
    sz=1;

    while(sz>0)
    {
        int x=h[1];
        swp(1,sz);
        pos[x]=0;
        sz--;

        if(sz>0)
            down(1);

        for(auto p:v[x])
        {
            int y=p.first,c=p.second;

            if(d[y]>d[x]+c)
            {
                d[y]=d[x]+c;

                if(pos[y]==0)
                {
                    h[++sz]=y;
                    pos[y]=sz;
                    up(sz);
                }
                else
                    up(pos[y]);
            }
        }
    }
}

void afisare()
{
    for(int i=2; i<=n; i++)
        fout<<(d[i]==INF?0:d[i])<<" ";
}

int main()
{
    citire();
    rezolvare();
    afisare();

    return 0;
}