#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50005

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

const int oo = (1 << 30); //infinity (max int)

vector < pair< int, int > > G[NMAX];
priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair<int, int> > > q;

int dist[NMAX], i, n, m, x, y, cost;
bool viz[NMAX];

void dijkstra(int nodInceput)
{
    dist[nodInceput] = 0;

    q.push({dist[nodInceput], nodInceput});
    viz[nodInceput] = true;

    while (!q.empty())
    {
        int nodCurent = q.top().second;
        q.pop();

        int nrvecini = G[nodCurent].size();
        for (i=0; i<nrvecini; i++)
        {
            int vecin = G[nodCurent][i].first;
            if (G[nodCurent][i].second + dist[nodCurent] < dist[vecin])
                dist[vecin] = G[nodCurent][i].second + dist[nodCurent];

            if (!viz[vecin])
                q.push({dist[vecin], vecin});
        }
    }
}

int main()
{
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> x >> y >> cost;
        G[x].push_back({y, cost});
        dist[i] = oo;
    }

    dijkstra(1);

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

    return 0;
}