#include <bits/stdc++.h>
#define MAX 1e9+7
#define N 50007

using namespace std;


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

int n,m;
bool ok;
vector<int>dist(N,MAX);
vector<bool>viz(N,0);
vector <pair<int,int>>a[N];
priority_queue<pair<int,int>> q;

void Citire()
{
    fin >> n >> m ;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        a[x].push_back( {c,y} );
    }
    fin.close();
}

void Update(int x)
{

    for(auto y:a[x])
    {
        int nod=y.second,cost=y.first;
        if( dist[nod]>dist[x]+cost )
        {
            dist[nod]=dist[x]+cost;
            if( !viz[nod] )q.push( {-dist[nod],nod} );
            viz[nod]=1;

        }


    }
}

void Dijkstra()
{
    dist[1]=0;
    q.push({0,1});
    viz[1]=1;
    while( !q.empty() )
    {
        int cur=q.top().second;
        q.pop();
        Update(cur);
    }
//    if( !ok )
//        fout << "Ciclu negativ!";
//    else
        for(int i=2;i<=n;i++)
            if( dist[i]==MAX )fout << "0 ";
            else fout << dist[i] << " ";
}



int main()
{
    Citire();
    Dijkstra();
    return 0;
}