#include <bits/stdc++.h>
#define N 50005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct muchie
{
    int nod,cost,lungime;
    bool operator < (const muchie x) const
    {
        return x.cost<cost;
    }
};
vector<muchie> g[N];
priority_queue<muchie>pq;
int n,m,costmin,d[N],lg[N];
bool viz[N];
void Citire()
{
    int x,y,i,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back({y,c});
        costmin=min(costmin,c);
    }
    for(i=1;i<=n;i++)
        for(int j=0;j<g[i].size();j++)
            g[i][j].cost-=costmin;
    /*for(i=1;i<=n;i++)
    {
        for(auto x:g[i]) cout<<x.nod<<" "<<x.cost<<"\n";
        cout<<"\n\n\n";
    }*/
}
void Dijkstra()
{
    pq.push({1,0,0});
    while(!pq.empty())
    {
        int nod=pq.top().nod;
        int cost=pq.top().cost;
        int lungime=pq.top().lungime;
        pq.pop();
        if(!viz[nod]) viz[nod]=1;
        else continue;
        d[nod]=cost;
        lg[nod]=lungime;
        for(auto x:g[nod])
           if(!viz[x.nod]) pq.push({x.nod,x.cost+cost,lungime+1});
    }
}
void Afisare()
{
    for(int i=2;i<=n;i++) fout<<d[i]+lg[i]*costmin<<" ";
}
int main()
{
    Citire();
    Dijkstra();
    Afisare();
    return 0;
}