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

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

struct muchie
{
    int nod, cost;
}temp;


vector<muchie> mu[100005];
bool vis[100005];
int dist[100005];


struct mycmp
{
    bool operator ()(int a, int b)
    {
        return dist[a] > dist[b];
    }
};

priority_queue<int, vector<int>, mycmp> pq;

void dijkstra(int start, int n)
{
    pq.push(start);
    for (int i = 2; i <= n; i++)
        dist[i] = 2e9;
    while(!pq.empty())
    {
        int aux = pq.top();
        vis[aux] = 1;
        //out<<aux<<" : ";

        for(int i = 0 ; i < mu[aux].size() ; i++)
        {
            if(!vis[mu[aux][i].nod])
            {
                //out<<mu[aux][i].nod<<" , ";
                pq.push(mu[aux][i].nod);
                if( dist[aux] + mu[aux][i].cost < dist[mu[aux][i].nod])
                {
                    dist[mu[aux][i].nod] = dist[aux] + mu[aux][i].cost;
                }
            }
        }
        //out<<'\n';

        pq.pop();
    }
}

void sortare(int n)
{
    for(int i = 1; i <= n ;i++)
    {
        //sort(mu[i].begin(), mu[i].end(), cmp);
    }
}

void afisare(int n)
{
    int i, j;
    for(int j = 1 ; j <= n; j++)
    {
        out<< j <<" : ";
        for(int i = 0 ; i < mu[j].size() ; i++)
        {
            out<<" nodu : " << mu[j][i].nod << " cost : " <<  mu[j][i].cost <<" , ";
        }
        out<<'\n';
    }
}

void citire(int m)
{
    int j, i;
    for(j = 1 ; j <= m; j++)
    {
        int y;
        in >> y >> temp.nod >> temp.cost;
        mu[y].push_back(temp);
    }
}

int main()
{
    int i, n, m;

    in >> n >> m;

    citire(m);

    //sortare(n);

//    afisare(n);
//    return 0;

    dijkstra(1, n);

    for(i = 2 ; i <= n ; i++)
    {
        out<<dist[i]<<" ";
    }
    return 0;
}