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

using namespace std;

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

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

int N, M;
vector< pair<int, int> > G[MAXN];
int Dmin[MAXN];

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

        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
    fin.close();
}

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

    memset(Dmin, INF, sizeof(Dmin));
    memset(InQueue, false, sizeof(InQueue));

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

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

        for (pair<int, int> it : G[nod])
            if (Dmin[it.first] > Dmin[nod] + it.second) {
                Dmin[it.first] = Dmin[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 << (Dmin[i] < INF ? Dmin[i] : 0) << ' ';
    fout.close();
}

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