#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <pair <int, int>> v[50001];

long long d[50001];

struct el
{
    long long c;
    int nod;
    bool operator <(const el &alt) const
    {
        if (c == alt.c)
            return nod < alt.nod;
        return c > alt.c;
    }
};

priority_queue <el> p;
bool b[50001];

int main()
{
    int n, m, i, j, x, y, z;
    fin >> n >> m;
    for (i = 1; i<=m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for (i = 1; i<=n; i++)
        d[i] = 1ll<<50;
    d[1] = 0;
    p.push({0, 1});
    for (i = 1; i<n; i++)
    {
        while (p.empty() == 0 && b[p.top().nod] == 1)
            p.pop();
        if (p.empty() == 1)
            break;
        x = p.top().nod;
        p.pop();
        b[x] = 1;

        for (j = 0; j<v[x].size(); j++)
            if (d[v[x][j].first] > d[x] + v[x][j].second)
            {
                d[v[x][j].first] = d[x] + v[x][j].second;
                p.push({d[v[x][j].first], v[x][j].first});
            }
    }
    for (i = 2; i<=n; i++)
    {
        if (d[i] < (1ll<<50))
            fout << d[i] << ' ';
        else
            fout << "0 ";
    }
    return 0;
}