#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define DM 50005
#define MAX 50000000
using namespace std;

struct bl
{
    int b, l;
};

vector <bl> graf [DM];
int mini [DM]; //lungimea minima de la 1 la drumul curent

void BFS (int vf)
{
    int i;

    queue <int> q;
    q . push (vf);

    while (!q . empty ())
    {
        vf = q . front ();
        for (i = 0; i < graf [vf] . size (); ++ i)
        {
            if (mini [vf] + graf [vf] [i] . l < mini [graf [vf] [i] . b])
            {
                mini [graf [vf] [i] . b] = mini [vf] + graf [vf] [i] . l;
                q . push (graf [vf] [i] . b);
            }
        }
        q . pop ();
    }

}



int main()
{
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");

    int n, m, a, b, c, i;
    bl cr;

    f >> n >> m;

    for (i = 1; i <= n; ++ i)
        mini [i] = MAX;

    for (i = 1; i <= m; ++ i)
    {
        f >> a >> b >> c;
        cr . b = b;
        cr . l = c;
        graf [a] . push_back (cr);
    }

    mini [1] = 0;
    BFS (1);

    for (i = 2; i <= n; ++ i)
    {
        if (mini [i] == 50000000) g << "0 ";
        else g << mini [i] << " ";
    }

    g << "\n";

    return 0;
}