#include <fstream>
#include <stdlib.h>
#define NMax 100
#define inf 10000
using namespace std;

fstream fin("dijkstra.in",ios::in);
fstream fout("dijkstra.out",ios::out);

struct GRAF{int y,cost;};

GRAF *A[NMax];
int *pre,*d,n,x0;
bool *viz;

void Initializare()
{
    int i,x,y,c,m;
    fin>>n>>m;
    x0=1;

    pre=(int*)realloc(pre,(n+1)*sizeof(int));
    d=(int*)realloc(d,(n+1)*sizeof(int));
    viz=(bool*)realloc(viz,(n+1)*sizeof(bool));

    for(i=1;i<=n;i++)
    {
        A[i]=(GRAF*)realloc(A[i],sizeof(GRAF));
        A[i][0].cost=0;//in A[x][0].cost tin minte cati vecini are x
        pre[i]=x0;
        d[i]=inf;
        viz[i]=false;
    }

    for(i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        A[x][0].cost++;
        A[x]=(GRAF*)realloc(A[x],(A[x][0].cost+1)*sizeof(GRAF));
        A[x][A[x][0].cost].y=y;
        A[x][A[x][0].cost].cost=c;
    }

    viz[x0]=true; pre[x0]=0;
    for(i=1;i<=A[x0][0].cost;i++)
        d[A[x0][i].y]=A[x0][i].cost;
    d[x0]=0;
}

void Dijkstra()
{
    int nrVfSel=0,dMin,VfMin,i;
    while(nrVfSel<n)
    {
        //gasesc drumul cel mai scurt
        dMin=inf;
        for(i=1;i<=n;i++)
            if(!viz[i]&&dMin>d[i])
            {
                dMin=d[i];
                VfMin=i;
            }
        //marchez varful gasit
        viz[VfMin]=true;
        nrVfSel++;
        for(i=1;i<=A[VfMin][0].cost;i++)
            if(d[A[VfMin][i].y]>d[VfMin]+A[VfMin][i].cost&&!viz[A[VfMin][i].y])
            {
                d[A[VfMin][i].y]=d[VfMin]+A[VfMin][i].cost;
                pre[A[VfMin][i].y]=VfMin;
            }
    }
}



void Afisare()
{
    for(int i=2;i<n;i++)
    fout<<d[i]<<" ";
    fout<<d[n];
    fout.close();
}

int main()
{
    Initializare();
    Dijkstra();
    Afisare();

    return 0;
}