#include <fstream>
#include <set>
#include <vector>

using namespace std;

const int N = 50005, oo = 2e9;
typedef pair <int, int> pii;

vector <pii> L[N];
set <pii> s;
int d[N], n;

void Read ()
{
    ifstream fin ("dijkstra.in");
    int m;
    fin >> n >> m;
    while (m--)
    {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }
}

void Dijkstra ()
{
    for (int i = 2; i <= n; i++)
        d[i] = oo;
    s.insert({0, 1});
    while (!s.empty())
    {
        int currvertex = s.begin() -> second;
        s.erase(s.begin());
        for (auto next : L[currvertex])
            if (d[next.first] > d[currvertex] + next.second)
            {
                if (d[next.first] < oo)
                    s.erase(s.find({d[next.first], next.first}));
                d[next.first] = d[currvertex] + next.second;
                s.insert({d[next.first], next.first});
            }
    }
    ofstream fout ("dijkstra.out");
    for (int i = 2; i <= n; i++)
        if (d[i] < oo) fout << d[i] << " ";
        else fout << "0 ";
    fout << "\n";
    fout.close();
}

int main()
{
    Read();
    Dijkstra();
    return 0;
}