#include <bits/stdc++.h>
using namespace std;
struct edge{int to;int cost;};
int V,E,N,k,l,d[50002],src=1;
int cst;
edge temp;
bool visited[50002];
vector<vector<edge> >g;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
        freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin>>V>>E;
    g.resize(V+1);
    for(int i=0;i<E;i++){
            cin>>k>>l>>cst;
            temp.to=l;
            temp.cost=cst;
            g[k].push_back(temp);
                        }
                      //  cin>>src;
                        queue<int>q;
                        for(int i=0;i<=V;i++)
                        d[i]=99999;
                        d[src]=0;
                    q.push(src);
                    while(!q.empty())
                    {
                        int v=q.front();
                        q.pop();
                        for(int i=0;i<g[v].size();i++)
                        {
                            if(d[g[v][i].to]>d[v]+g[v][i].cost){
                        d[g[v][i].to]=d[v]+g[v][i].cost;
                            if(!visited[g[v][i].to]){
                        q.push(g[v][i].to);
                        visited[g[v][i].to]=1;
                        }
                            }
                        }
    visited[v]=0;

                    }
                    for(int i=2;i<=V;i++){
                            if(d[i]<9999)
                        cout<<d[i]<<" ";
                    else cout<<"0 ";
                    }

    return 0;
}