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

using namespace std;

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

const int DMAX = 100005;
const int oo = 1 << 30;

unsigned int n, m;
unsigned int D[DMAX];
bool InCoada[DMAX];

vector < pair <unsigned int, unsigned int> > G[DMAX];

struct compara
{
    bool operator()(unsigned int x, unsigned int y)
    {
        return D[x] > D[y];
    }
};

priority_queue <unsigned int, vector<unsigned int>, compara> coada;

void read()
{
    f >> n >> m;

    for (unsigned int i = 1; i <= m; i++)
    {
        unsigned int x, y, cost;

        f >> x >> y >> cost;

        G[x].push_back(make_pair(y, cost));
    }
}

void dijkstra(unsigned int nodStart)
{
    for (unsigned int i = 2; i <= n; i++)
        D[i] = oo;

    D[nodStart] = 0;

    coada.push(nodStart);
    InCoada[nodStart] = true;

    while (!coada.empty())
    {
        unsigned int nodCurent = coada.top();
        coada.pop();

        InCoada[nodCurent] = false;

        for (unsigned int i = 0; i < G[nodCurent].size(); i++)
        {
            unsigned int vecin = G[nodCurent][i].first;
            unsigned int cost = G[nodCurent][i].second;

            if (D[nodCurent] + cost < D[vecin])
            {
                D[vecin] = D[nodCurent] + cost;

                if (InCoada[vecin] == false)
                {
                    coada.push(vecin);
                    InCoada[vecin] = true;
                }
            }
        }
    }
}

void show()
{
    for (unsigned int i = 2; i <= n; i++)
    {
        if (D[i] == oo)
            g << 0 << ' ';
        else
            g << D[i] << ' ';
    }
}

int main()
{
    read();
    dijkstra(1);
    show();

    return 0;
}