#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
#define NMAX 65536
#define INF 0x3f3f3f3f
#define pb(a) push_back(a)
vector<long> veci[NMAX],cost[NMAX];
long n,m,a,b,c,i,d[NMAX],nod; 
int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    for (i=1;i<n+1;++i){
        scanf("%ld %ld %ld",&a,&b,&c);
        veci[a].pb(b);
        cost[a].pb(c);
        }
    //---------------------------
    bitset <NMAX> iq;
    queue<int> q;
    memset(d, INF, sizeof(d));
    
    d[1]=0;
    q.push(1);
    iq[1]=1;
    
    while (!q.empty()){
          nod=q.front();
          q.pop();
          iq[nod]=0;
          for (i=0;i<veci[nod].size();++i)
              if (d[nod]+cost[nod][i]<d[veci[nod][i]]){
                 d[veci[nod][i]]= d[nod] +cost[nod][i];
                 if (!iq[veci[nod][i]]){
                    q.push(veci[nod][i]);
                    iq[veci[nod][i]]=1;
                    }
                 }
          }
    for (i=2;i<n+1;++i)
        printf("%ld ",( d[i]<INF ? d[i] : 0));
    
                                    
    
    return 0;
}