#include <iostream>
#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


void dijkstra ()
{
    int m,x,y,z,n;
    f>>n>>m;
    int gasit [n+1],distanta[n+1],matrice [n+1][n+1],vizitat [n+1];

    int i,j,minim,punct;
    for (i=1;i<=n;i++)
    {
        gasit [i] = 0;
        distanta [i] = 0;
        vizitat [i] = 0;
    for (j=1;j<=n;j++)
        matrice [i][j] =0;
    }
    for (i=1;i<=n;i++)
    {
        f>>x>>y>>z;
        matrice [x][y] = z;
    }

    for (i=2;i<=n;i++)
        distanta [i] = matrice [1][i];
    distanta [1] = 0;

    for (i=2;i<=n;i++)
    {
        minim = 100001;
        for (j=1;j<=n;j++)
            if (gasit [j] ==0 && distanta [j] )
                if (minim > distanta [j])
                {
                    minim = distanta [j];
                    punct = j;
                }

        gasit [punct] = 1;

        for (j=2;j<=n;j++)
        {
            int valoare = matrice [punct][j] + distanta [punct];
            if (vizitat [j] == 0)
            {
                if ((valoare < distanta [j] || distanta [j] == 0) && matrice [punct][j] >0)
                    distanta [j] = valoare;
            }
        }

    }

    for (i=2;i<=n;i++)
        g << distanta [i] << " ";
}



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