Contest4_meetInTheMiddle

import java.io.*;
import java.util.*;
public class Solution{
  public static int[] dj_prim(LinkedList[] ln,int src){
    int v=ln.length;
    int d []=new int[v];
    int check[]=new int[v];
    for(int i=0;i<v;i++){
      d[i]=Integer.MAX_VALUE;
    }
    d[src]=0;
    for(int i=0;i<v;i++){
      int u=minVertex(d,check);
      for(int j=0;j<ln[u].size();j++){
        String str=ln[u].get(j).toString();
        StringTokenizer st=new StringTokenizer(str,",");
        int t=Integer.parseInt(st.nextToken());
        int dst=Integer.parseInt(st.nextToken());
        if(check[t]!=-1 && d[u]!=Integer.MAX_VALUE && d[u]+dst<d[t]){
          d[t]=d[u]+dst;
        }

      }
    }
    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;
  }
  public static void main(String[]args) {
    Scanner in=new Scanner(System.in);
    int v=in.nextInt();
    int e=in.nextInt();
    LinkedList[] ln=new LinkedList[v];
    for(int i=0;i<v;i++)
      ln[i]=new LinkedList<String>();
    String str;
    int vc=0;
    String s[];
    for(int i=0;i<e;i++){
      int from=in.nextInt();
      int to=in.nextInt();
      int w=in.nextInt();
      ln[from].add(to+","+w);
    }
  if(v==1)
    System.out.println(0);
  else{
  int d[]=dj_prim(ln,0);
  int d1[]=dj_prim(ln,v-1);
  int min =Integer.MAX_VALUE;
  int result=-1;
  int i;
  for(i=0;i<v;i++){
    if(d[i]+d1[i]<min &&(d[i]<=100000 && d1[i]<=100000)){
      result=i;
    min=d[i]+d1[i];
    }



  }

  System.out.println(result);
  }
  }

}