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

using namespace std;

int n, m;
int d[50004];
vector <int> a[50004];
vector <int> c[50004];
priority_queue <int> q;

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

void DJ()
{
    int i, L, nod;
    for (i = 1; i <= n; i++)
        d[i] = 1e9;
    d[1] = 0;
    q.push(1);
    while (!q.empty())
    {
        nod = q.top();
        q.pop();
        L = a[nod].size();
        for (i = 0; i < L; i++)
            if (d[nod] + c[nod][i] < d[a[nod][i]])
            {
                d[a[nod][i]] = d[nod] + c[nod][i];
                q.push(a[nod][i]);
            }
    }
}

int main()
{
    int i, x, y, cost;
    fin >> n >> m;
    for (i = 0; i < m; i++)
    {
        fin >> x >> y >> cost;
        a[x].push_back(y);
        c[x].push_back(cost);
    }
    DJ();
    for (i = 2 ; i<= n;i++)
        fout << (d[i] == 1e9 ? 0 : d[i]) << " ";
    fout << "\n";
    fout.close();
    fin.close();
    return 0;
}