#include <fstream>
#include <set>
#include <vector>
#include <limits.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <pair<int,int> >a[50001];
multiset <pair<unsigned int,int> > b;
multiset <pair<unsigned int,int> > ::iterator it;
unsigned int x,y,z,nre[50001],n,k,i,cost,nod,d[50001];
int main()
{
    f>>n>>k;
    for(i=1;i<=k;i++){
        f>>x>>y>>z;
        a[x].push_back(make_pair(z,y));

    }
    for(i=1;i<=n;i++){
        nre[i]=a[i].size();
        d[i]=INT_MAX;
    }
    b.insert(make_pair(0,1));
    d[1]=0;
    while(!b.empty()){
        it=b.begin();
        cost=(*it).first;
        nod=(*it).second;
        b.erase(it);
        for(i=0;i<nre[nod];i++){
               int nodact=a[nod][i].second;
                int costact=d[a[nod][i].second];
                if(costact>cost+a[nod][i].first){
                    d[nodact]=cost+a[nod][i].first;
                    b.insert(make_pair(d[nodact],nodact));
                }

        }
    }
    for(i=2;i<=n;i++){
        if(d[i]==INT_MAX)
            g<<0<<' ';
        else
            g<<d[i]<<' ';

    }
    return 0;
}