#include <iostream>
#include <fstream>
#include <vector> 
#include <queue>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int MAXN=50001;
const int INF=1e9;

vector <pair<int,int>> adj[MAXN];
priority_queue <pair<int,int>> pq;

int dist[MAXN];

void dijkstra(int src,int n)
{
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    dist[1]=0;
    pq.push({0,src});
    while(!pq.empty())
    {
        int d=-pq.top().first;
        int nod=pq.top().second;
        pq.pop();
        
        if(dist[nod]!=d)
            continue;
            
        for( auto edge : adj[nod] )
        {
            if(edge.first+d<dist[edge.second])
                {dist[edge.second]=edge.first+d;
            pq.push({-edge.first-d,edge.second});}
            
        }
    }
}

int main()
{
    int n,m,a,b,c;
    in>>n>>m;
    for(int i=1;i<=n;i++)
    {
        in>>a>>b>>c;
        adj[a].push_back({c,b});
    }
    
    dijkstra(1,n);
    
    for(int i=2;i<=n;i++)
        if(dist[i]==MAXN)
            out<<0<<" ";
        else
            out<<dist[i]<<' ';

    return 0;
}