//DETECTEAZA CIRCUITELE DE COST NEGATIV!!


#include <fstream>
#include <vector>

using namespace std;

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

const int M_MAX = 250000;
const int N_MAX = 50000;

struct muchie {
    int x, y, cost;
};
muchie Edges[M_MAX + 1];

int D[N_MAX + 1];  //retine costul minim al drumului pana la fiecare nod, care trece doar prin nodurile vizitate
int N, M;

void bellmanford() {
    bool ok = false;
    int cnt = 1;
    while (!ok && cnt <= N) {
        ok = true;
        for(int i = 1; i <= M; ++i)
            if(D[Edges[i].x] + Edges[i].cost < D[Edges[i].y])
                ok = false, D[Edges[i].y] = D[Edges[i].x] + Edges[i].cost;
        ++cnt;
    }
    //daca am gasit un circuit negativ
    if(cnt == N + 1);
        //fa gat
}

int main() {

    in >> N >> M;
    for (int i = 1; i <= N; i++)
        D[i] = 1000000;
    D[1] = 0;

    for (int i = 1; i <= M; i++) {
        in >> Edges[i].x >> Edges[i].y >> Edges[i].cost;
        if(Edges[i].x == 1)
            D[Edges[i].y] = Edges[i].cost;
    }

    bellmanford();

    for (int i = 2; i <= N; i++)
        if (D[i] < 1000000)
            out << D[i] << ' ';
        else
            out << 0 << ' ';

    return 0;
}