#include <bits/stdc++.h>
#define INF 2100000000
#define nod second
#define cost first
/// TONI BO$$ was here
/// #MLC

using namespace std;

struct edge
{
    int nod,cost;
};

vector < edge > G[50001];
int mindist[50001];
priority_queue < pair <int,int> , vector < pair <int,int> >  , greater < pair <int,int> > > q;

int main()
{
    int n,m,i,x,y,c;
    ios::sync_with_stdio(false);
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        edge aux;
        aux.nod=y;
        aux.cost=c;
        G[x].push_back(aux);
    }
    for(i=2; i<=n; i++)
        mindist[i]=INF;
    q.push({0,1});
    while(!q.empty())
    {
        pair <int,int> u=q.top();
        q.pop();
        if(mindist[u.nod]==u.cost)
            for(auto w : G[u.nod])
                if(mindist[w.nod]>mindist[u.nod]+w.cost)
                {
                    mindist[w.nod]=mindist[u.nod]+w.cost;
                    q.push({mindist[w.nod],w.nod});
                }
    }
    for(i=2; i<=n; i++)
        if(mindist[i]!=INF)
            cout<<mindist[i]<<" ";
        else
            cout<<"0 ";

    return 0;
}