#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

#define FILEIN "dijkstra.in"
#define FILEOUT "dijkstra.out"

const int MAXN = 50005;
const int INF = 0x3f;

struct edge {
    int src;
    int dest;
    int weight;

    edge(int src, int dest, int weight) {
        this->src = src;
        this->dest = dest;
        this->weight = weight;
    }
};

int N, M;
//vector< pair<int, int> > G[MAXN];
vector<edge> G;
int dist[MAXN];

void ReadData() {
    ifstream fin(FILEIN);
    fin >> N >> M;
    for (int i = 0; i < N; i++) {
        int a, b, c;

        fin >> a >> b >> c;
        edge e = edge(a, b, c);
        G.push_back(e);
    }
    fin.close();
}

void Solve() {
    //bool InQueue[MAXN]; // bitset
//    queue<int> Q;

    memset(dist, INF, sizeof(dist));
//    memset(InQueue, false, sizeof(InQueue));

    dist[1] = 0;
//    Q.push(1);
//    InQueue[1] = true;

    for (int i = 1; i <= N - 1; i++) {
        for (edge e : G) {
            int u = e.src;
            int v = e.dest;
            int weight = e.weight;

            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
            }
        }
    }

/*
    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        InQueue[nod] = false;

        for (pair<int, int> it : G[nod])
            if (dist[nod] + it.second < dist[it.first]) {
                dist[it.first] = dist[nod] + it.second;
                if (!InQueue[it.first]) {
                    Q.push(it.first);
                    InQueue[it.first] = true;
                }
            }
    }
    */
}

void WriteData() {
    ofstream fout(FILEOUT);

    for (int i = 2; i <= N; i++)
        fout << (dist[i] < INF ? dist[i] : 0) << ' ';
    fout.close();
}

int main()
{
    ReadData();
    Solve();
    WriteData();
    return 0;
}