#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int N = 50000;

struct muchie
{
    int nod;
    int cost;
};


vector<muchie> vecin[1 + N];
queue<int> coadaBF;

//int vizite[N + 1];
int dist[N + 1];
bool inCoada[N + 1];

int main()
{
    FILE *fin, *fout;

    fin = fopen("dijkstra.in", "r");
    fout = fopen("dijkstra.out", "w");

    int n, m;

    fscanf(fin, "%d %d", &n, &m);

    for(int i = 1; i <= m; i++)
    {
        int u, v, c;
        fscanf(fin, "%d%d%d", &u, &v, &c);
        vecin[u].push_back({v, c});
    }

    coadaBF.push(1);
    inCoada[1] = true;
    for(int i = 2; i <= n; i++)
        dist[i] = 0x3fffffff;

    while(!coadaBF.empty())
    {
        int nod = coadaBF.front();
        coadaBF.pop();
        inCoada[nod] = false;
        for (muchie m : vecin[nod]) {
        {
            //muchie m = vecin[nod][i];
            if(dist[m.nod] > dist[nod] + m.cost)
                dist[m.nod] = dist[nod] + m.cost;
            if(!inCoada[m.nod])
            {
                coadaBF.push(m.nod);
                inCoada[m.nod] = true;
            }
            //vizite[m.nod]++;
        }
    }

    for(int i = 2; i <= n; i++)
    {
        if(dist[i] == 0x3fffffff)
            dist[i] = 0;
        fprintf(fout, "%d ", dist[i]);
    }

    return 0;
}