#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 100001;
const int M = 200001;

int lst[N], vf[M], c[M], urm[M], n, m, nr, q[N], d[N];
bool inq[N];

void adauga (int x, int y, int cost){
    nr++;
    vf[nr] = y;
    c[nr] = cost;
    urm[nr] = lst[x];
    lst[x] = nr;
}

int main()
{
    int x, y, cost, p, u, poz;
    in >> n >> m;
    for (int i = 1; i <= m; i++){
        in >> x >> y >> cost;
        adauga(x, y, cost);
    }
    for (int i = 1; i <= n; i++)
        d[i] = 1000000000;

    d[1] = 0;
    p = 0;
    u = 1;
    q[u] = 1;
    inq[1] = true;
    while (p != u){
        p++;
        x = q[p];
        inq[x] = false;
        poz = lst[x];
        while (poz != 0){
            y = vf[poz];
            cost = c[poz];
            if (d[x] + cost < d[y])
            {
                d[y] = d[x] + cost;
                if (!inq[y]){
                    q[++u] = y;
                    inq[y] = true;
                }
            }
            poz = urm[poz];
        }
    }

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