#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int N=50005;
const int oo=2000000000;
vector <pair <int,int> > a[N];

int nh,n,m,d[N],poz[N];
bool viz[N];

struct heap
{
    int dist,nod;
};

heap h[N];
void citire()
{
    int x,y,z,i;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }
}

void swapp(int i,int j)
{
    swap(h[i],h[j]);
    poz[h[i].nod]=i;
    poz[h[j].nod]=j;
}
void urca(int nod)
{
    while(nod>1 && h[nod].dist>h[nod/2].dist)
    {
        swapp(nod,nod/2);
        nod=nod/2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    //out<<h[fs]<<" "<<h[fd]<<" "<<h[bun]<<endl;
    if(fs<=nh && h[fs].dist< h[bun].dist)
        bun=fs;
    if(fd<=nh && h[fd].dist< h[bun].dist)
        bun=fd;
    if(bun!=p)
    {
        swapp(p,bun);
        coboara(bun);
    }
}

void sterge(int nod)
{
    swapp(1,nh);
    nh--;
    coboara(nod);
}
void Dijkstra()
{
    int k,i;
    h[1].dist=0;
    h[1].nod=1;
    for(i=2;i<=n;i++)
    {
        h[i].dist=oo;
        h[i].nod=i;
    }
    for(i=2; i<=n; i++)
        d[i]=oo;
    //for(k=1; k<=nh; k++)
    while(nh > 0)
    {
        //int distanta=h[k].dist;
        int nod=h[1].nod;//h[k].nod;
        sterge(1);
        // viz[nod]=1;
        for(i=0; i< a[nod].size(); i++)
        {
            int vecin=a[nod][i].first,cost=a[nod][i].second;
            if(d[vecin]>d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;
                h[poz[vecin]].dist=d[vecin];
                h[poz[vecin]].nod=vecin;
                urca(poz[vecin]);
            }

        }
    }
}
int main()
{
    citire();
    nh=n;
    Dijkstra();
    for(int i=1; i<=n; i++)
        if(d[i]==oo)
            d[i]=0;
    for(int i=2; i<=n; i++)
    {
        out<<d[i]<<" ";
    }
    return 0;
}