#include <iostream>
#include <fstream>
#include <vector>
#define alot 2e9

using namespace std;
int n, m;

class nod{
public:
    int id;
    vector <pair <int, int> > vecini;
};

vector <nod> G ;
vector <int> dist;
vector <bool> vizitat;

int main()
{
    int i, x, y, z, minim, minpoz, neviz;
    ifstream g ("dijkstra.in");
    ofstream h ("dijkstra.out");

    g>>n>>m;
    neviz = n-1;

    G.resize(n+1);
    vizitat.resize(n+1);
    dist.resize(n+1);

    for(i=0;i<m;i++)
    {
        g>>x>>y>>z;
        G[x].vecini.push_back(make_pair(y, z));
        G[x].id = x;

    }

    dist[1]=0;
    for(i=2;i<=n;++i)
        dist[i]=alot;

    while (neviz)
    {
        minim=alot;
        for(i=1;i<=n;++i)
            if(minim > dist[i] && !vizitat[i])
            {
                minim = dist[i];
                minpoz = i;
            }
        if (minim == alot)      //toate nodurile sunt unreachable
            break;
        vizitat[minpoz]=1;
        --neviz;

        for (i = 0; i<G[minpoz].vecini.end() - G[minpoz].vecini.begin();++i)
            if(dist[minpoz] + G[minpoz].vecini[i].second < dist[G[minpoz].vecini[i].first])
                dist[G[minpoz].vecini[i].first] = dist[minpoz] + G[minpoz].vecini[i].second;

    }

    for (i=2;i<=n;++i)
        h<<dist[i]<<" ";
}