#include <bits/stdc++.h>
#define inf 169696969
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,dp[50005];
bool ap[50005];
vector<pair<int,int> > lista[50005];
struct compare{
    bool operator () (int d1, int d2)
    {
        return dp[d1]>dp[d2];
    }
};
priority_queue<int,vector<int>,compare> pq;
void dijkstra(int node)
{
    ap[node]=true;
    for(int i=1; i<=n; i++)
        dp[i]=inf;
    dp[node]=0;
    pq.push(node);
    while(!pq.empty())
    {
        int nod = pq.top();
        pq.pop();
        ap[nod] = 0;
        for(auto x:lista[nod])
        {
            if(dp[x.first]>dp[nod]+x.second)
            {
                dp[x.first]=dp[nod]+x.second;
                if(!ap[x.first])
                {
                    pq.push(x.first);
                    ap[x.first]=1;
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
        if(i==node) continue;
        else if(dp[i]==inf) out << "0 ";
        else out << dp[i] << ' ';
}
int main()
{
    in >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        lista[x].push_back({y,c});
    }
    dijkstra(1);
    return 0;
}