#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <chrono>
#include <numeric>
#include <iomanip>

#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>  
#include <stack>
#include <queue>
#include <list>

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;

// template <class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);

#define M 1000000007

#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()

// auto lim=unique(all(v));
// v.resize(distance(v.begin(), lim));

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

        auto hash1 = splitmix64(p.first+FIXED_RANDOM);
        auto hash2 = splitmix64(p.second+FIXED_RANDOM);
 
        return hash1^hash2;
    }
};

ll gcd(ll a,ll b){
    ll r;
    while(b){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}

template<class T> T nxt() {
    T x;
    cin >> x;
    return x;
}

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

vl computeDistancesSlow(const int& n,const vector<vector<pair<int,ll>>>& edges,
    const int& startingNode,
    const ll& maxValue)
{
    // Apply Dijkstra's algorithm without using a priority queue/set
    // O(n*n+m) time
    vb visited(n+1,0);
    vl distance(n+1,maxValue);

    distance[startingNode]=0;
    while(1){
        int currentNode=-1;
        ll minDistance=maxValue;
        for(int i=1;i<=n;++i){
            if(!visited[i]&&distance[i]<minDistance){
                minDistance=distance[i];
                currentNode=i;
            }
        }

        if(currentNode==-1){
            break;
        }

        visited[currentNode]=true;
        for(pair<int,ll> pair:edges[currentNode]){
            int neighborNode;
            ll edgeDistance;
            tie(neighborNode,edgeDistance)=pair;

            distance[neighborNode]=min(distance[neighborNode],distance[currentNode]+edgeDistance);
        }
    }

    return distance;
}

void DijkstraUsingSet(const int& n,const vector<vector<pair<int,ll>>>& edges,
    const int& startingNode,
    const ll& maxValue,
    vl& distance,vi& predecesor
){
    // O(n log(n) + m log(n)) time
    distance.assign(n+1,maxValue);
    predecesor.assign(n+1,0);

    set<pair<ll,int>> q;
    distance[startingNode]=0;
    q.insert({0,startingNode});

    while(!q.empty()){
        auto p=*q.begin();
        int node;
        ll nodeDistance;
        tie(nodeDistance,node)=p;

        q.erase(q.begin());

        for(auto p:edges[node]){
            int neighborNode;
            ll cost;
            tie(neighborNode,cost)=p;

            if(nodeDistance+cost<distance[neighborNode]){
                q.erase({distance[neighborNode],neighborNode});

                distance[neighborNode]=nodeDistance+cost;
                predecesor[neighborNode]=node;
                
                q.insert({distance[neighborNode],neighborNode});
            }
        }
    }
}

void SolveSlow(){
    int n,m;
    ll maxValue=1e18;
    cin>>n>>m;

    vector<vector<pair<int,ll>>> edges(n+1);
    for(int i=0;i<m;++i){
        int x,y;
        ll c;
        cin>>x>>y>>c;
        edges[x].push_back({y,c});
    }

    vl distance=computeDistancesSlow(n,edges,1,maxValue);

    for(int i=1;i<=n;++i){
        if(distance[i]==maxValue){
            distance[i]=0;
        }
    }

    for(int i=2;i<=n;++i){
        cout<<distance[i]<<' ';
    }
}

void SolveFaster(){
    int n,m;
    ll maxValue=1e18;
    cin>>n>>m;

    vector<vector<pair<int,ll>>> edges(n+1);
    for(int i=0;i<m;++i){
        int x,y;
        ll c;
        cin>>x>>y>>c;
        edges[x].push_back({y,c});
    }

    vl distance;
    vi predecesor;
    DijkstraUsingSet(n,edges,1,maxValue,distance,predecesor);

    for(int i=1;i<=n;++i){
        if(distance[i]==maxValue){
            distance[i]=0;
        }
    }

    for(int i=2;i<=n;++i){
        cout<<distance[i]<<' ';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    // std::string file="";
    // std::ifstream in(file+".in");
    // std::streambuf *cinbuf = std::cin.rdbuf(); //save old buf
    // cin.rdbuf(in.rdbuf()); //redirect std::cin
    
    // std::ofstream out(file+".out");
    // std::streambuf *coutbuf = std::cout.rdbuf(); //save old buf
    // cout.rdbuf(out.rdbuf()); //redirect std::cout

    SolveFaster();

    // std::cin.rdbuf(cinbuf);   //reset to standard input again
    // std::cout.rdbuf(coutbuf); //reset to standard output again

    return 0;
}