//
//  A.cpp
//
//  Created by Vlad Turcuman on 24/09/2017.
//  Copyright © 2017 Vlad Turcuman. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <set>

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define NMax 50100
#define oo 1000000000

using namespace std;

int n;
vector<pii> edges[NMax];
int best[NMax];

multiset<pii> que;
multiset<pii>::iterator link[NMax];
bool inQue[NMax];

pii tmp;

void Dijkstra()
{
    memset(best,0x7f, sizeof(best));
    
    best[1] = 0;
    que.insert({0,1});
    
    while(que.size())
    {
        tmp = *que.begin();
        que.erase(que.begin());
        inQue[tmp.sc] = 0;
        
        for(auto j : edges[tmp.sc])
        {
            if(j.sc + tmp.fs < best[j.fs])
            {
                best[j.fs] = j.sc + tmp.fs;
                if(inQue[j.fs])
                    que.erase(link[j.fs]);
                que.insert({best[j.fs], j.fs});
                inQue[j.fs] = 1;
            }
        }
    }
}


int main()
{
    int m,from,to,cost;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>from>>to>>cost;
        edges[from].push_back({to,cost});
    }
    
    Dijkstra();
    
    for(int i=2;i<=n;i++)
        cout<<best[i]<<' ';
    
    return 0;
    
}


/*
 
Test Cases:
 
 
 
*/