#include <fstream>
#include <vector>
#include <set>
#define INF 1<<30
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
struct chestii{
    int cost,nod;
};
vector <chestii> lista[50003];
int dist[50003];
int main()
{
    int n,p,x,y,c,pp,min1,nod,vec,i,j;
    chestii aux;
    cin>>n>>m;
    p=1;
    while(cin>>x>>y>>c)
    {
        aux.nod=y;
        aux.cost=c;
        lista[x].push_back(aux);
    }
    for(i=1;i<=n;i++)
        dist[i]=INF;
    dist[p]=0;
    set<pair<int,int> > multime;
    multime.insert(make_pair(0,p));
    pp=0;
    while(!multime.empty())
    {
        nod=multime.begin()->second;
        min1=multime.begin()->first;
        multime.erase(multime.begin());
        for(j=0;j<lista[nod].size();j++)
        {
            vec=lista[nod][j].nod;
            if(dist[vec]>min1+lista[nod][j].cost)
            {
                if(dist[vec]!=INF)
                    multime.erase(multime.find(make_pair(dist[vec],vec)));
                dist[vec]=min1+lista[nod][j].cost;
                multime.insert(make_pair(dist[vec],vec));
            }


        }
    }
    for(i=1;i<=n;i++)
    {
        if(i==p)
            cout<<"0 ";
        else
        if(dist[i]==INF)
            cout<<"0 ";
        else
            cout<<dist[i]<<" ";
    }
    return 0;
}