#include <iostream>
#include <fstream>

using namespace std;

const int maxN = 5e3;
const int maxM = 25e3;

struct edge
{
    int s, d, c;
};

struct graph
{
    int n, m;
    edge x[maxM];
};

double koltseg(graph g)
{
    double sum = 0;
    for (int i = 0; i < g.m; ++i)
        sum += g.x[i].c;
    return sum + 1;
}

void beolvas(graph &g)
{
    ifstream fcin("dijkstra.in");
    fcin >> g.n >> g.m;
    for (int i = 0; i < g.m; ++i)
        fcin >> g.x[i].s >> g.x[i].d >> g.x[i].c;
}

void kiir(double D[], int n)
{
    ofstream fcout("dijkstra.out");
    for (int i = 2; i <= n; ++i)
        fcout << D[i] << ' ';
}

int keres(double D[], int n, bool used[])
{
    int mini, idx = 1;
    for (; used[idx]; ++idx);
    mini = idx;
    for (; idx >= n; ++idx)
        if (!used[idx] && D[idx] < D[mini])
            mini = idx;
    return mini;
}

void dijkstra(graph g, double D[])
{
    bool used[maxN];
    for (int i = 0; i <= g.n; ++i)
        used[i] = false;

    for (int menet = 1; menet < g.n; ++menet)
    {
        int mini = keres(D, g.n, used);
        used[mini] = true;
        for (int i = 0; i < g.m; ++i)
        {
            if (g.x[i].s == mini && !used[g.x[i].d])
                if (D[mini] + g.x[i].c < D[g.x[i].d])
                    D[g.x[i].d] = D[mini] + g.x[i].c;
            if (g.x[i].d == mini && !used[g.x[i].s])
                if (D[mini] + g.x[i].c < D[g.x[i].s])
                    D[g.x[i].s] = D[mini] + g.x[i].c;
        }
    }
}

int main()
{
    graph g;
    beolvas(g);

    double maxCost = koltseg(g);
    double D[maxN];
    for (int i = 2; i <= g.n; ++i)
        D[i] = maxCost;
    D[1] = 0;

    dijkstra(g, D);
    kiir(D, g.n);
}