/* Subject: Contest submission for problem #3, file 3.c */
/* twang22@imail.EECS.Berkeley.EDU */
/* Thu Sep 18 00:44:10 PDT 2003 */
/*___CONTEST_SUBMISSION___ twang22 3 */
/* name: Ming-Hsiu Wang
 * estimated time ~ 1.5 hrs
 * actual time ~ 2.5 hrs
 *   Except for stumbling with remembering certain c syntax, the coding of
 * this program was pretty straight foward.  */    

#include "contest.h"

#define MAX_NUM_OF_VERTICES 1024

int snarkDist[MAX_NUM_OF_VERTICES]; // distance of snark to any node
int boroDist[MAX_NUM_OF_VERTICES]; // distant of borogrove to any node
int path[MAX_NUM_OF_VERTICES]; // shortest path (for borogrove)

struct edge
{
  int weight; 
  int otherV; // the other vertex this node is connected to
};

struct graph
{
  int numOfVertices;  // number of vertices
  int degree[MAX_NUM_OF_VERTICES]; // degree of each vertices
  struct edge edges[MAX_NUM_OF_VERTICES][MAX_NUM_OF_VERTICES]; // adjacency matrix
};


// run dijkstra algorithm
static void dijkstra(struct graph *gr, int start, int numOfVertices, int* dist) {
	int marked[MAX_NUM_OF_VERTICES]; // whether the vertext is marked
	int i;						
	int v=start, w; // vertices (v for the current vertex, w for the one it is connected to)	
	int weight;			
	int smallestDist;
	
			

	// initialize the array
	for (i=0; i<=numOfVertices; i++) {
		marked[i] = 0;
		dist[i] = INT_MAX;
		path[i] = INT_MAX;
	}
	
	
	// set start distance to be 0
	dist[start] = 0;
	

	while (marked[v]==0) {
	    marked[v] = 1;
	    
		for (i=0; i<gr->degree[v]; i++) {
			w = gr->edges[v][i].otherV;
			weight = gr->edges[v][i].weight;
			
			// if distance is the same, but the path is to a smaller-value room
			if(dist[w] == (dist[v]+weight) && v<path[w]) {
				path[w]=v;
			} else if (dist[w] > (dist[v]+weight)) {
			  dist[w] = dist[v]+weight;
			  path[w]=v;
			} 
		}
		
		
		v=start;
		smallestDist = INT_MAX;
		// get the next unmarked vertex with the smallest distance
		for (i=0; i<=gr->numOfVertices; i++) 
			if ((marked[i] == 0) && (smallestDist >= dist[i])) {
				smallestDist = dist[i];
				v = i;
			}
	}


}


int main () {
  int numOfVertices;
  struct graph* gr=(struct graph*) malloc(sizeof(struct graph));
  int i,j;
  int room1, room2;
  int weight;
  int nextRoom;


  // initialize
  memset(gr->degree,0,MAX_NUM_OF_VERTICES+1);


  for(i=0;i<MAX_NUM_OF_VERTICES;i++) 
    for(j=0; j<MAX_NUM_OF_VERTICES; j++) {
      gr->edges[i][j].otherV=-1;
      gr->edges[i][j].weight=0;
    }
  

	// get inputs
  scanf("%d",&numOfVertices);
  gr->numOfVertices=numOfVertices;

  while( scanf("%d %d %d",&room1,&room2,&weight)!=EOF) {
    gr->edges[room1][gr->degree[room1]].weight=weight;
    gr->edges[room2][gr->degree[room2]].weight=weight;
    gr->edges[room2][gr->degree[room2]].otherV=room1;
    gr->degree[room1]++;
    gr->degree[room2]++;
  }


	// perform dijkstra on snark
  dijkstra(gr,2,numOfVertices,snarkDist);
  
  // do dijkstra in reverse, thus allowing boro to always pick the 
  // smaller-value room when the shortest distance is the same
  dijkstra(gr,0,numOfVertices,boroDist); 

// start from room 1
  nextRoom = 1;
  do {
	// for each room in the path, check if the snark can get there first
  	nextRoom=path[nextRoom];
  	if(snarkDist[nextRoom] < 0) continue;
  	if((boroDist[1]-boroDist[nextRoom]) > 2*snarkDist[nextRoom]) {
  		printf("Snark eats\n");
  		exit(0);
  	} 
  	
  } while (nextRoom);
   
   // else borogove escapes
   printf("Borogove escapes\n");
   exit(0); 
}