#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 5e4 + 5;
const int oo = (1 << 31) - 1;

int n, m;
int dist[Nmax];
vector <pair <int, int> > L[Nmax];
bitset <Nmax> viz;

struct Coada
{
    int nod, dist;

    bool operator <(const Coada &e) const
    {
        return dist > e.dist;
    }
};

priority_queue <Coada> q;

int main()
{
    fin >> n >> m;

    int x, y, c;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }

    for(int i = 1; i <= n; i++)
        dist[i] = oo;

    dist[1] = 0;
    q.push({1, 0});

    while(!q.empty())
    {
        x = q.top().nod;
        q.pop();

        if(!viz[x])
        {
            viz[x] = 1;

            for(auto i : L[x])
                if(dist[i.first] > dist[x] + i.second)
                {
                    dist[i.first] = dist[x] + i.second;
                    q.push({i.first, dist[i.first]});
                }
        }
    }

    for(int i = 2; i <= n; i++)
        fout << (dist[i] == oo ? 0 : dist[i]) << " ";

    fin.close();
    fout.close();
    return 0;
}