#include<fstream>
#include<iomanip>
using namespace std;

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

const int INF = 1<<25;
const int N = 1000;
const int M = 1000;
const int START = 1;

int dist[N][N];
int cost[N];
int viz[N];

int n,m;


void afismat(int mat[][N], int n, int m)
{
    int i,j;

    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j)
            if(j>i)
                if(mat[i][j]!=INF) out<<setw(3)<<mat[i][j];
                else out<<setw(3)<<"@";
            else if(j==i) out<<setw(3)<<"#";
            else out<<setw(3)<<"~";
        out<<"\n";
    }
    out<<"\n";
}

void afisvec(int v[], int n)
{
    int i;

    for(i=1; i<=n; ++i)
        if(v[i]!=INF) out<<setw(3)<<v[i];
        else out<<setw(3)<<"@";
    out<<"\n";
}

void afissol()
{
    int i;
    for(i=2; i<=n; ++i) out<<cost[i]<<" ";
}

void init()
{
    int i,j;

    for(i=1; i<=n; ++i) cost[i] = INF;

    cost[START] = 0;
    viz[START] = 0;

    /// Todo: remove pentru liste
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            dist[i][j] = INF;
}

void cit(int &n, int &m, int distante[][N])
{
    int i,a,b,x;

    in>>n>>m;

    init();

    for(i=1; i<=m; ++i)
    {
        in>>a>>b>>x;
        distante[a][b] = distante[b][a] = x;
    }
}

int nextNod() /// Caut cel mai apropiat nod de subgraful meu
{
    int i,minim,minimPoz;

    minimPoz = INF;
    minim = INF;
    for(i=1; i<=n; ++i)
        if(viz[i]==0 && cost[i]<minim)
        {
            minim = cost[i];
            minimPoz = i;
        }

    return minimPoz;
}

void updateVecini(int nod)  /// Updatez distantele pentru vecinii nodului 'nod' (minime noi)
{
    int i;

    for(i=1; i<=n; ++i)
    {
        cost[i] = min(cost[i], cost[nod] + dist[nod][i]);
    }
}

void extindArbore()
{
    int poz=0;

    int pas=0;

    poz = nextNod();
    while(poz != INF)
    {
        viz[poz] = 1;
        updateVecini(poz);

        /*out<<"Pas = "<<(++pas)<<"\n";
        out<<"cost: "; afisvec(cost, n);
        out<<"vec:  "; afisvec(viz, n);
        out<<"\n";*/

        poz = nextNod();
    }
}

int main()
{
    int i,a,b;

    cit(n, m, dist);
    //afismat(dist, n, m);
    extindArbore();
    afissol();

    return 0;
}