#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define MAXN 5001

int N,M,x,y,i;
vector <int> A[MAXN];
int cost[MAXN][MAXN], d[MAXN], viz[MAXN];
queue <int> Q;

void citire()
{
    f >> N >> M;
    for (i = 1; i <= M; i++)
    {
        f >> x >> y;
        A[x].push_back(y);
        f>>cost[x][y];
    }
    f.close();
}

void Dijkstra()
{
    int nod;

    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();
        //cout<<nod<<" ";
        for (auto j: A[nod])
        {   //cout<<nod<<" "<<j<<" "<<cost[nod][j]<<endl;
            if (!viz[j] && d[j] > d[nod] + cost[nod][j])
            {
                    d[j] = d[nod] + cost[nod][j];
                    Q.push(j);
            }
            viz[j] = 1;
        }
    }
}

int main()
{
    // folosesc liste de vecini pentru retinerea grafului
    citire();

    for (int i = 2; i <= N; ++i)
        d[i] = MAXN;

    memset(viz, 0, sizeof(viz));

    d[1] = 0;
    Q.push(1);

    Dijkstra();

    for (i=2; i<=N; i++)
        if (d[i] == MAXN)
            cout<<0<<" ";
        else
            g<<d[i]<<" ";

    g.close();
    return 0;
}