#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax = 50000;
const int INF = 1e9;

int n,m;

int d[nmax + 5];


struct mch{
    int to;
    int cost;
};
struct q_nod{
    int nod;
    int cost;
    bool operator < (const q_nod& b) const {
    return cost < b.cost;}
};


vector <mch> v[nmax + 5];

priority_queue <q_nod> q;



int main()
{
    fin>>n>>m;
    for (int i = 1; i <= m; i++)
    {
        mch a;
        int x;
        fin>>x;
        fin>>a.to>>a.cost;
        v[x].push_back(a);
    }
    for (int i = 1;i<=n;i++) d[i] = INF;
    d[1] = 0;

    q.push({1, 0});
    while (!q.empty())
    {
        q_nod top = q.top();
        q.pop();
        if (d[top.nod] != top.cost)
            continue;
        for (auto &i : v[top.nod]) {
            int new_cost = top.cost + i.cost;
            if (new_cost < d[i.to])
                q.push({i.to, new_cost}), d[i.to] = new_cost;
        }
    }
    for (int i = 2; i <= n; i++)
        fout<<(d[i] != INF ? d[i] : 0)<<' ';

}