#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define maxnod 50001
#define MINIM 1<<30
#define cost first
#define to second
int noduri,muchii,i;
vector< pair<int,int> > matrix[maxnod];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coada;
FILE *in,*out;
vector<int> dist(maxnod,MINIM);
void dijkstra(int startNode);
int main()
{
    int nod1,nod2,costul;
    in=fopen("dijkstra.in","rt");
    out=fopen("dijkstra.out","wt");
    fscanf(in,"%d%d",&noduri,&muchii);
    for(i=1;i<=muchii;i++)
    {
        fscanf(in,"%d %d %d",&nod1,&nod2,&costul);
        matrix[nod1].push_back(make_pair(nod2,costul));
    }

    dijkstra(1);

    for(i=1;i<=noduri;i++)

        fprintf(out,"%d ",dist[i]);

    return 0;
}

void dijkstra(int startNode)
{
    dist.at(startNode)=0;
    vector<pair<int,int> >::iterator vecin,end;
    pair<int,int> nodCurent;
    coada.push(make_pair(0,startNode));
    while(!coada.empty())
    {
        nodCurent=coada.top();
        coada.pop();
        end=matrix[nodCurent.to].end();
        for(vecin=matrix[nodCurent.to].begin();vecin!=end;++vecin)
            if(dist[vecin->to]>dist[nodCurent.cost]+vecin->cost)
            {
                dist[vecin->to]=dist[nodCurent.cost]+vecin->cost;
                coada.push(make_pair(dist[vecin->to],vecin->to));
            }
    }

}