#include <stdio.h>
#define maxn 50001
#define inf 1<<30
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");

struct graf{
  int nod, cost;
  graf *adr_urm;
};

int n,m;
int d[maxn],q[maxn],t[maxn],k;
graf *a[maxn];

void adauga(int where, int what, int cost){
  graf *q;
  q->nod=what;
  q->cost=cost;
  q->adr_urm=a[where];
  a[where]=q;
}

void citire(){
  int i,x,y,z;
  fscanf(f,"%d %d",&n,&m);
  for(i=1;i<=m;i++)fscanf(f,"%d %d %d",&x,&y,&z);
  adauga(x,y,z);
}

void swapy(int x,int y){
  int temp;
  temp=q[x];
  q[x]=q[y];
  q[y]=temp;
}


void downheap(unsigned int d[],int n,int i){
  int fiu;
  while((i<<1)<=n){
    fiu=i<<1;
    if(fiu|1<=n&&d[q[fiu|1]]<d[q[fiu]])fiu|=1;
    if(d[q[fiu]]<d[q[i]]){
      swapy(fiu,i);
      i=fiu;
    }
    else break;
  }
}

void upheap(int i){
  int val;
  val=q[i];
  while (i>1 && d[val]<d[q[i>>1]]){
    q[i]=q[i>>1];
    i>>=1;
  }
  q[i]=val;
}
  
void dijkstra(){
  int i,k,min;
  for(i=1;i<=n;i++){
    q[i]=i;
    t[i]=0;
    d[i]=inf;
  }
  k=n;
  d[1]=0;
  for(i=k>>1;i>0;i--) downheap (d,n,i);
  while(k>0&&d[q[1]]<inf){
    min=q[1];
    q[1]=q[k];
    k--;
    downheap(d,k,1);
    graf *lista = a[min];
    while(lista){
      if(d[lista->nod]>d[min]+lista->cost)
    

}
int main(){
  citire();
   
  fclose(f);
  fclose(g);
  return 0;
}