#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N=50002;
const int INF=1e9+1;
struct succesor{
    int vf,c;
};
int d[N],h[N],poz[N],n,nh,m;
vector <succesor> s[N];

void schimba(int p,int q)
{
    swap(h[p],h[q]);
    poz[h[p]]=p;
    poz[h[q]]=q;
}

void urca(int p)
{
    while(d[h[p]]<d[h[p/2]])
    {
        schimba(p,p/2);
        p=p/2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,optim=p;
    if(fs<=nh && d[h[fs]]<d[h[optim]])
    {
        optim=fs;
    }
    if(fd<=nh && d[h[fd]]<d[h[optim]])
    {
        optim=fd;
    }
    if(optim!=p)
    {
        schimba(p,optim);
        coboara(optim);
    }
}

void sterge(int p)
{
    if(p==nh)
    {
        nh--;
    }
    else
    {
        schimba(p,nh);
        poz[nh--]=-1;
        urca(p);///nu se va intampla daca p=1
        coboara(p);
    }
}

void dijkstra(int x0)
{
    ///initializam vectorul d
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        h[++nh]=i;
        poz[i]=nh;
    }
    d[x0]=0;
    urca(poz[x0]);
    while(nh>0)///cat timp heap-ul nu e vid
    {
        int x=h[1];///varful cu distanta de la x0 la el minima
        sterge(1);
        for(auto p:s[x])
        {
            int y=p.vf;
            int c=p.c;
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                ///pred[y]=x; daca as vrea sa refac drumurile
                urca(poz[y]);
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        succesor aux;
        aux.c=c;
        aux.vf=y;
        s[x].push_back(aux);
    }
    f.close();
    dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INF)
        {
            d[i]=0;
        }
        g<<d[i]<<" ";
    }
    return 0;
}