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

#define Nmax 50010
#define INFI 0x3f3f3f3f

using namespace std;

int n, m, x, y, z, i, viz[Nmax], bun[Nmax], nc;
queue <int> coada;
struct cost
{
    int nod;
    int c;
};
vector <cost> muchie[Nmax];

int main()
{
    ifstream f("dijkstra.in");
    ofstream h("dijkstra.out");
    f >> n >> m;
    memset (bun, INFI, sizeof(bun));
    for (i = 1; i <= m; ++i)
    {
        f >> x >> y >> z;
        muchie[x].push_back(cost {y, z});
    }
    f.close();
    coada.push(1);
    viz[1] = 1;
    bun[1] = 0;
    while (!coada.empty())
    {
        nc = coada.front();
        coada.pop();
        viz[nc] = 0;
        for (i = 0; i < muchie[nc].size(); ++i)
        {
            if (bun[muchie[nc][i].nod] > bun[nc] + muchie[nc][i].c)
            {
                if (!viz[muchie[nc][i].nod])
                {
                    coada.push(muchie[nc][i].nod);
                    viz[muchie[nc][i].nod] = 1;
                }
                bun[muchie[nc][i].nod] = bun[nc] + muchie[nc][i].c;
            }
        }
    }
    for (i = 2; i <= n; ++i)
        if (bun[i] == INFI)
            h << "0 ";
        else
            h << bun[i] << " ";
    h.close();
    return 0;
}