#include <bits/stdc++.h>
#define cin in
#define cout out
#define eb emplace_back 
#define ll long long
#define pii pair<int,int>
using namespace std;

const string fn("dijkstra");

ifstream in(fn + ".in");
ofstream out(fn + ".out");

const int MAX=5e4;

priority_queue<pii,vector<pii>,greater<pii>> pq;
vector<pii> G[MAX+5];
ll cost[MAX+5];

void dijkstra(int src) 
{
    pq.emplace(0,src);
    cost[src]=0;
    while(!pq.empty())
    {
        int w,node;
        tie(w,node)=pq.top();
        pq.pop();
        for(auto x: G[node]) 
            if(cost[x.first]>w+x.second)
            {
                cost[x.first]=w+x.second;
                pq.emplace(cost[x.first],x.first);
            }
    }
}

void write(int n) 
{
    for(int i=1;i<=n;i++,cout<<' ')
        if(cost[i]==LLONG_MAX) cout<<0;
        else cout<<cost[i];
}

int main()
{
    int n,m,u,v,w;
    cin>>n>>m;
    while(m--) 
    {
        cin>>u>>v>>w;
        G[u].eb(v,w);
    }
    for(int i=2;i<=n;i++) cost[i]=LLONG_MAX;
    dijkstra(1);
    write(n);
    return 0;
}