#include <iostream>
#include<vector>
#include<queue>
#include<fstream>
#include<utility>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int MMAX= 250001;
const int NMAX = 50001;
const int INFINIT=100000000;
int vizitat[NMAX];
int drum[MMAX];
queue<int>Q;
vector<int>P[NMAX];
vector<int>D[MMAX];
vector<pair<int,int> >v;


int main()
{int n,m,a,b,c;
f>>n>>m;
for(int i=1;i<=n;i++)
{
    f>>a>>b>>c;
    P[a].push_back(b);
    v.push_back(make_pair(a,b));
    D[a].push_back(c);
}
Q.push(1);
vizitat[1]=1;
drum[1]=0;
for(int i=2;i<=n;i++)
    drum[i]=INFINIT;
while(!Q.empty())
{
    a=Q.front();
    vizitat[a]=0;
    for(int i=0;i<P[a].size();i++)
        if(drum[P[a][i]]>(drum[a]+D[a][i]))
        {drum[P[a][i]]=drum[a]+D[a][i];
        if(vizitat[P[a][i]]==0)
           {Q.push(P[a][i]);
            vizitat[P[a][i]]=1;
        }
}
Q.pop();
}
for(int i=2;i<=n;i++)
    if(drum[i]!=INFINIT)
    g<<drum[i]<<" ";
else g<<0<<" ";
    return 0;
}