#include <bits/stdc++.h>
#define Nmax 50005
#define INF 1000000000
#define pb push_back

using namespace std;

struct Edge
{
    int nod,cost;
    bool operator <(const Edge &A) const
    {
        return cost<A.cost;
    }
};
vector <Edge> L[Nmax];
priority_queue <Edge> Q;
int dp[Nmax],n;

inline void Dijkstra()
{
    int i;
    Edge w,w1;
    for(i=2;i<=n;++i) dp[i]=INF;
    w.nod=1; w.cost=0; Q.push(w);
    while(!Q.empty())
    {
        w=Q.top(); Q.pop();
        for(auto it : L[w.nod])
        {
            w1.nod=it.nod; w1.cost=w.cost+it.cost;
            if(dp[w1.nod]>w1.cost)
            {
                dp[w1.nod]=w1.cost; Q.push(w1);
            }
        }
    }
}

int main()
{
    int i,m,x;
    Edge w;
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>w.nod>>w.cost;
        L[x].pb(w);
    }
    Dijkstra();
    for(i=2;i<=n;++i) cout<<dp[i]<<" ";
    cout<<"\n";
    return 0;
}