#include<fstream>
#include<cstring>
#define nmax 50000
#define inf -1
#include <vector>
#include <set>
using namespace std;

vector <int> a[nmax];
vector <int> b[nmax];
set <int> f[nmax];


int v[nmax],n,t[nmax];

void schimb_fii(int cui,int cu_cat)
{
    set<int>::iterator it;
    for(it=f[cui].begin();it!=f[cui].end();it++)
    {
        v[*it]=v[*it]-cu_cat;
        schimb_fii(*it,cu_cat);
    }
}

void schimb_tata(int cine, int cu_cine,int cu_cat)
{

    f[cu_cine].insert(cine);
    f[t[cine]].erase(cine);
    t[cine]=cu_cine;
    int val_veche,diferenta;
    val_veche=v[cine];
    t[cine]=cu_cine;
    v[cine]=v[cu_cine]+cu_cat;
    diferenta=val_veche-v[cine];
    schimb_fii(cine,diferenta);
}



void dij()
{
    int i;
    v[1]=0;
    vector<int>::iterator ita,itb;
    for(i=1;i<=n;i++)
    {
        for(ita=a[i].begin(),itb=b[i].begin();ita!=a[i].end();ita++,itb++)
        {
            if(t[*ita]==0 || v[*ita]>v[i]+v[*itb])
             {

                 schimb_tata(*ita,i,*itb);
             }

        }
    }
}


void citire()
{
    ifstream in("dijkstra.in");
    int i,x,y,val,m;
    in>>n>>m;
    /*for(i=1;i<=n;i++)
    t[i]=-1;*/
    for(i=1;i<=m;i++)
        {
            in>>x>>y>>val;
            a[x].push_back(y);
            b[x].push_back(val);
        }
    in.close();
}

void afisare()
{
    int i;
    ofstream out("dijkstra.out");
    for(i=2;i<=n;i++)
    {
        if(v[i]==-1) v[i]=0;
        out<<v[i]<<' ';
    }
    out.close();
}
int main()
{
    int m;
    citire();
    dij();
    afisare();

}