#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int dim = 50005;

vector <pair <int,int> > vec[dim];
priority_queue <pair <int,int>, vector<pair <int,int> >, greater<pair <int,int> > > pq;
int n,m,dist[dim],viz[dim];

void Dijkstra(int nod,int d)
{
    while (!pq.empty())
    {
        pair <int,int> acum = pq.top();
        pq.pop();

        if (!viz[acum.second])
        {
            dist[acum.second] = acum.first + d;
            for (auto v : vec[acum.second])
            {
                pq.push({dist[acum.second] + v.first , v.second});
            }
            viz[acum.second] = 1;
        }
    }
}

int main()
{
    int x,y,z;
    in >> n >> m;
    for (int i=1; i<=m; i++)
    {
        in >> x >> y >> z;
        vec[x].push_back({z,y});
    }
    pq.push({0,1});
    Dijkstra(1,0);
    for (int i=2; i<=n; i++)
    {
        out << dist[i] << " ";
    }
    return 0;
}