#include <iostream>
#include <fstream>
#define NMaxVf 5001
#define Inf 20002
int n , x0;
double c[NMaxVf][NMaxVf];
int pre[NMaxVf], M[NMaxVf];
double d[NMaxVf];
void Initializare();
void Afisare();

using namespace std;

int main()
{

    int  i, VfMin, j;
    double dMin;
    Initializare();
for(j=1;j<n;j++) {
        dMin = Inf;
        for(i=1; i <= n;i++)
            if(!M[i] && dMin>d[i])
        {
            dMin = d[i];
            VfMin = i;
        }
        M[VfMin] = 1;
        for(i=1;i <= n;i++)
            if(!M[i] && d[i] > dMin + c[VfMin][i])
        {
            pre[i] = VfMin;
            d[i] = dMin + c[VfMin][i];
        }
}
    Afisare();
return 0;
}

void Initializare()
{
    int i, j, m, x, y;
    double c1;
    ifstream fin("dijkstra.in");
    fin >> n >> m ;
    for(i = 1;i <= n;i++)
        for(j = i+1;j <= n;j++)
            c[j][i] = c[i][j] = Inf;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c1;
        c[x][y] = c1;

    }
    x0 = 1;

    for(i=1;i<=n;i++)
    {
        d[i] = c[x0][i];
        pre[i] = x0;

    }
    M[x0] = 1; pre[x0] = 0;
    fin.close();
}
void Afisare()
{
    ofstream fout("dijkstra.out");
    int i, j, lg, dr[NMaxVf];
    for(i=1;i<=n;i++)
        if(i!=x0)
    {   if(d[i] == Inf)
            d[i] = 0;
         fout << d[i] << " ";
        dr[0] = i;
        lg = 0;
        while(pre[dr[lg]])
        {
            lg++;
            dr[lg] = pre[dr[lg-1]];
        }

    }
    fout.close();
}