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

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int NMAX = 50005;
const int inf = (1 << 30);

vector < pair < int, int > > G[NMAX];

int dist[NMAX], n, m;

void citire()
{
    int x, y, z;
    cin >> n >> m;

    for(int i = 1 ; i <= m ; i++)
        cin >> x >> y >> z,
            G[x].push_back({y, z});
}

void init()
{
    for(int i = 1 ; i <= n ; i++)
        dist[i] = inf;
    dist[1] = 0;
}

void rez()
{
    set < pair <int, int> > h;
    h.insert(make_pair(0, 1));

    while(!h.empty())
    {
        int nod = h.begin()->second;
        int d = h.begin()->first;
        h.erase(h.begin());

        vector < pair < int, int > >::iterator it;

        for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
        {
            int newnod = it->first;
            int cost = it->second;

            if(dist[newnod] > dist[nod] + cost )
            {
                if(dist[newnod] != inf)
                    h.erase( h.find( {dist[newnod], newnod} ) );

                dist[newnod] = dist[nod] + cost;
                h.insert(make_pair(dist[newnod], newnod));
            }
        }

    }

}

void afis()
{
    for (int i = 2; i <= n; ++i)
    {
        if (dist[i] == inf)
            dist[i] = 0;
        cout << dist[i] << ' ';
    }
    cout << '\n';
}

int main()
{
    citire();
    init();
    rez();
    afis();
    return 0;
}