#include <iostream>
#include <queue>
#include <fstream>
#include <cstring>
#include <vector>


using namespace std;

int n, m, dist[50005], in_coada[50005];
const int nmax = 20000*50000;
struct cmp
{
    bool operator ()(int x, int y)
    {
        return dist[x] > dist[y];
    }
};
priority_queue<int, vector<int>, cmp> pq;
vector< pair<int, int> > list_vec[50005];

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


void citire()
{
    fin>>n>>m;
    int u, v, i, c;

    for(i = 1; i <= m; ++i)
    {
        fin>>u>>v>>c;
        list_vec[u].push_back(make_pair(v, c));
    }
}
void dijkstra(int start)
{
    int curent, vecin, cost, i;

    for(i = 1;  i<=n; ++i)
        dist[i] = nmax;
    pq.push(start);
    dist[start] = 0;
    in_coada[start] = 1;

    while(!pq.empty())
    {
        curent = pq.top();
        pq.pop();
        in_coada[curent] = 0;
        for(i = 0; i < list_vec[curent].size(); ++i)
        {
            vecin = list_vec[curent][i].first;
            cost = list_vec[curent][i].second;
            if(dist[curent] + cost < dist[vecin])
            {
                dist[vecin] = dist[curent] + cost;
                if(in_coada[vecin] == 0)
                {
                    pq.push(vecin);
                    in_coada[vecin] = 1;
                }
            }
        }
    }
}
int main()
{
    citire();

    dijkstra(1);
    for(int i = 2; i <= n; ++i)
    {
        if(dist[i] != nmax)
            fout<<dist[i]<<' ';
        else
            fout<<-1<<' ';
    }

    return 0;
}