#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define inf 100000000
#define Nmax 22161
int n,m;

int mat[Nmax][Nmax];
int v[Nmax];
int ni[Nmax];
int d[Nmax];

void citire()
{
    int i,a,b,c;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        mat[a][b]=c;
    }
}

void di(int ns)
{
    int i,ok,mi,nod;
    for(i=1;i<=n;i++)
    {
        d[i]=mat[ns][i];
        ni[i]=ns;
    }
    v[ns]=1;
    ok=1;
    while(ok==1)
    {
        mi=inf;
        for(i=1;i<=n;i++)
        {
            if(d[i]<mi&v[i]==0)
                {
                    mi=d[i];
                    nod=i;
                }
        }
            v[nod]=1;
            if(mi==inf) ok=0;
            else
                {
                    for(i=1;i<=n;i++)
                    {
                        if(v[i]==0&&d[nod]+mat[nod][i]<d[i])
                        {
                            d[i]=d[nod]+mat[nod][i];
                            ni[i]=nod;
                        }
                    }
                }

    }
}

int main()
{
    int i,j;
    in>>n>>m;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            mat[i][j]=inf;
        }
    }
    citire();
    di(1);

    for(i=2;i<=n;i++)
    {
        out<<d[i]<<" ";
    }
    return 0;
}