CONTEST4_MEET_iN_THE_MIDDLE_FAHIM

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package contest;



import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


/**
 *
 * @author acer
 */
public class solution1 {
    public static int node;
    //public static int [] d;
    public static int [] parent;
    public static int [] [] matrix;
     public static int [] color;
    public static LinkedList[] ln;

     public static PriorityQueue<Integer> q =new PriorityQueue<Integer>();


    public static void main(String[] args) {
  //float a=0;

            Scanner scn=new Scanner(System.in);



            node=scn.nextInt();


            int edge=scn.nextInt();


         //   out.println(v);
            matrix=new int[node][node];
            color=new int[node];
            parent=new int[node];
            //d=new int[node];
             ln=new LinkedList[node];

              for(int i=0;i<node;i++){

      ln[i]=new LinkedList<String>();
              }

              int i=0;
            while(i<edge)
            {

            int x=scn.nextInt();
            int y=scn.nextInt();
            int w=scn.nextInt();

            ln[x].add(y+","+w);
            i++;
            }
            /*
            for(int k=0;k<node;k++){
      System.out.println(k+"=>");
      for(int j=0;j<ln[k].size();j++){

        String str=ln[k].get(j).toString();
          System.out.println(str);
      }
   }*/


          int []d=new int[node];
           int []d1=new int[node];


        d=dijkstra(0);
        d1=dijkstra(node-1);

       /* for(int p:d1){
            System.out.print(p+",");
        }*/
        int min =Integer.MAX_VALUE;
  int result=-1;

  for(int q=0;q<node;q++){
    if(d[q]+d1[q]<min &&(d[q]<=100000 && d1[q]<=100000)){
      result=q;
    min=d[q]+d1[q];
    }



  }

  System.out.println(result);


    }
    public static int [] dijkstra(int s) {
        int[]d=new int[node];
        //System.out.println("=========================");


       for(int i=0;i<node;i++) {

            d[i]=9999;
             //q.add(d[i]);
            color[i]=0;
            parent[i]=-1;

        }

    d[s]=0;
    parent[s]=-1;
    q.add(d[s]);

   for(int i=0;i<node;i++){
      int u=minVertex(d,color);
      for(int j=0;j<ln[u].size();j++){
        String str=ln[u].get(j).toString();
        String [] splitA;
        splitA=str.split(",");
        int t=Integer.parseInt(splitA[0]);
        int dst=Integer.parseInt(splitA[1]);
        if(color[t]!=1 && d[u]!=Integer.MAX_VALUE && d[u]+dst<d[t]){
          d[t]=d[u]+dst;
        }

      }
       //System.out.print(i+"=>");
   }
        //System.out.println();
   return d;

    }
    public static int minVertex(int d[],int check[]){
    int min=Integer.MAX_VALUE;
    int min_index=-1;
    for(int i=0;i<d.length;i++){
      if(check[i]!=1 && d[i]<=min){
        min=d[i];
        min_index=i;
      }


    }
    check[min_index]=1;
    return min_index;
  }




}