#include <stdio.h>

using namespace std;

#define NrNoduri 50000
#define NrMuchii 250000
#define Max 32767

void init(int );
struct StrMuchii
{
	int a,b,c; //nodul a legat de nodul b cu costul c
    
}Muchii[NrMuchii+1]; //Structura muchii

struct StrCoada
{
	int nod;
	int cost;
}Coada[NrNoduri+1]; //Structura Coada

int n,m;
int Costuri[NrMuchii+1]; // Structura Costurile nodurilor din nodul 'start'



void AdaugaCoada(int nod, int cost,int &elemCoada);

void ExtrageCoada(int &elemCoada,int &x,int &y);
void Dijkstra(int elemCoada);
           
int main() // functia main este aici <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
{
            int x,y,c,start,elemCoada=0;//n-noduri m-muchii
            //printf("Nodul de pornire:");
            //scanf("%i",&start);
            freopen("dijkstra.in","r",stdin);
            freopen("dijkstra.out","w",stdout);
    start=1;
    //printf("n,m=?");
            scanf("%i%i",&n,&m);
            init(start);
            
            for(int i=1;i<=m;i++)//citire din fisier graf
            {
                //printf("\n%i. x,y,c=",i);
                scanf("%i%i%i",&x,&y,&c);
                Muchii[i].a=x;
                Muchii[i].b=y;
                Muchii[i].c=c;
            }
            
            Coada[1].nod=start;
            Coada[1].cost=0;
            elemCoada++;
            Dijkstra(elemCoada);
    for(int i=1;i<=n;i++)
    {
        if(Costuri[i]!=Max)
        //printf("De la nodul %i pana la nodul %i costul este: %i\n",start,i,Costuri[i]);
        else
            //printf("Nu se poate ajunge de la nodul %i la nodul %i\n",start,i);
    }
    fclose(stdin);
    fclose(stdout);
     return 0;
}
   // se termina functia main <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
           
           
void init(int start)  // functia de initializare init
{
    for(int i=1;i<=n;i++)
       Costuri[i]=Max;
    Costuri[start]=0;
}


void AdaugaCoada(int nod, int cost,int &elemCoada) //adauga un element nou in coada
{
    //nu cred ca e nevoie de for
    for(int i=1;i<=elemCoada;i++)
        if(Coada[i].nod==nod && Coada[i].cost>cost)
        {
            Coada[i].cost=cost;
            return ;
        }
    // sf for------            
    
    elemCoada++;
    Coada[elemCoada].nod=nod;
    Coada[elemCoada].cost=cost;
}



void ExtrageCoada(int &elemCoada,int &x,int &y) // functie de extragere din coada, returneaza valorile x si y
{
	int poz,min;
	poz=1;
	min=Coada[poz].cost;
	for(int i=2;i<=elemCoada;i++)
		if(Coada[i].cost<min)
		{
			poz=i;
			min=Coada[i].cost;
		}
    x=Coada[poz].nod;
    y=Coada[poz].cost;
    for(int j=poz+1;j<=elemCoada;j++)
    {
        Coada[j-1]=Coada[j];
    }
    elemCoada--;
    //return poz;
}

void Dijkstra(int elemCoada) // algoritmul principal
{
    int nodC,costC; // nodul extras din coada si costul lui
    while(elemCoada!=0)
    {
        ExtrageCoada(elemCoada,nodC,costC);
        for(int i=1;i<m;i++)
        {
            if(nodC == Muchii[i].a)
                if(costC+Muchii[i].c < Costuri[Muchii[i].b])
                {
                    Costuri[Muchii[i].b]=costC+Muchii[i].c;
                    AdaugaCoada(Muchii[i].b,costC+Muchii[i].c,elemCoada);
                }
            
            //if(nodC<Muchii[i].a) //terminare for fortat
            //    i=m;
        }
    }
}