#include <fstream>
#include <vector>
#define inf 1e9
#define NMAX 50004
using namespace std;

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

struct varf
{
    int x, c;
};

int n, x0=1;

vector <varf> G[NMAX]; ///liste de adiacenta cu costuri

bool uz[NMAX];
int cmin[NMAX];

int H[NMAX]; ///aici retin vf organizate ca un heap dupa CMIN
int nr;
int poz[NMAX];
///poz[x]=0 daca x nu e in heap
///pozitia pe care se afla in heap x

void citire();
void dijkstra();
void afisare();

void inserare(int H[],int &n,int x);
void combinare(int H[],int &n,int poz);
int ExtrageMin(int H[],int &n);
void upgrade(int H[],int n,int poz);

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
    int i, j, c,m;
    varf aux;
    cin>>n>>m;
    while (cin>>i>>j>>c)
    {
        //in lista de adiacenta a lui i trebuie sa adaug perechea j,k
        aux.x=j;
        aux.c=c;
        G[i].push_back(aux);
    }

    for (i=1; i<=n; i++)
        cmin[i]=inf;
    cmin[x0]=0;

    H[1]=x0;
    nr=1;
    poz[x0]=1;

}

void dijkstra()
{
    int i,j,vfmin,x,cost;

    for (i=1; i<=n; i++)
    {
        ///calculez vfmin
        vfmin=ExtrageMin(H,nr);
        if(cmin[vfmin]==inf)
        return;
        ///selectez vfmin
        uz[vfmin]=1;
        ///optimizez eventual costurile minime
        for (j=0; j<G[vfmin].size(); j++)
        {
            x=G[vfmin][j].x;
            cost=G[vfmin][j].c;
            if (!uz[x] && cmin[x]>cmin[vfmin]+cost)
            {
                cmin[x]=cmin[vfmin]+cost;
                ///upgrade
                ///promovez vf x in Heap pana ajunge la poz corecta
                if(poz[x])
                    upgrade(H,nr,poz[x]);
                else
                    inserare(H,nr,x);
            }
        }
    }
}

void afisare()
{
    int i, j, cnt;
    for (i=2; i<=n; i++)
    {
        if (cmin[i]==inf)
            cout<<0<<' ';
        else
        {
            cout<<cmin[i]<<' ';
        }
        //cout<<'\n';
    }
}

void inserare(int H[],int &n,int x)
{
    int fiu,tata;
    fiu=n+1;
    tata=fiu/2;
    while(tata && cmin[H[tata]]>cmin[x])
    {
        H[fiu]=H[tata];
        poz[H[tata]]=fiu;
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
    n++;
    poz[x]=fiu;
}

void combinare(int H[],int &n,int ppoz)
{
    ///combina H[poz] cu heap-urile (corecte!) vcu rad pe pozitiile 2poz
    int x=H[ppoz],fiu,tata;
    tata=ppoz;
    fiu=2*tata;
    while(fiu<=n)
    {
        if(fiu+1<=n&&cmin[H[fiu+1]]<cmin[H[fiu]])
            fiu++;
        if(cmin[H[fiu]]>=cmin[x])
            break;
        H[tata]=H[fiu];
        poz[H[fiu]]=tata;
        tata=fiu;
        fiu=2*tata;
    }
    H[tata]=x;
    poz[x]=tata;
}

int ExtrageMin(int H[],int &n)
{
    int minim=H[1];
    H[1]=H[n];
    n--;
    combinare(H,n,1);
    return minim;
}

void upgrade(int H[],int n,int ppoz)
{
    int fiu=ppoz,tata=fiu/2,aux;
    while(tata)
    {
        if(H[fiu]>=H[tata])
            break;

        ///interschimbare valori si pozitii
        aux=poz[H[fiu]]; poz[H[fiu]]=poz[H[tata]]; poz[H[tata]]=aux;

        aux=H[fiu];
        H[fiu]=H[tata];
        H[tata]=aux;

        fiu=tata;
        tata=fiu/2;
    }
}