#include <bits/stdc++.h>

#define graf vector<vector<pai>>
#define pai pair<int, int>
using namespace std;

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

struct pii{
    int dis_or;
    bool ok;
};
priority_queue <pai,vector<pai>,greater<pai> > f;
//array <pii, 10> ff;
vector<pii> ff;
graf a; int n, m; string r; int p1 = 1; pai p, pp;

void read();
void li();
void afis();

int main()
{
    read();
    li();
    afis();
    return 0;
}

void read()
{
    fin >> n >> m;
    a = graf(n+1);
    ff = vector<pii>(n+1);
    int x, y, z;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> z;
        p.second = y;
        p.first = z;
        a[x].push_back(p);
    }
}


void li()
{
    ff[p1].ok = true;
    ff[p1].dis_or = 0;
    for (pai i : a[p1])
    {
        if (ff[i.second].ok == false)
        {
            p.second = i.second;
            p.first = i.first + ff[i.second].dis_or;
            f.push(p);
        }
    }
    while (f.empty() == false)
    {
        p = f.top();
        f.pop();
        if (ff[p.second].ok == true)
            continue;
        //fout << p.second << ' ';
        ff[p.second].dis_or = p.first;
        ff[p.second].ok = true;

        for (auto i : a[p.second])
        {
            if (ff[i.second].ok == false)
            {
                pp.second = i.second;
                pp.first = i.first + ff[p.second].dis_or;
                f.push(pp);
            }
        }
    }
}

void afis()
{
    //fout << '\n';
    for (int i = 2; i <= n; i++)
    {
        //fout << i << ": ";
        fout << ff[i].dis_or << ' ';
    }
}