import java.util.Scanner;
import java.lang.Math;
import java.util.ArrayList;
public class TravellingCheap
{
  public static void main(String[] args)
  {
    Scanner in = new Scanner(System.in);
    
    String assignment = in.nextLine();
    
    if (assignment.trim().equals("Part 1"))
    {
      int N = in.nextInt();
      
      // northCost is the minimum cost to get to the northern island previously under consideration
      int northCost = 0;
      int southCost = 0;
      
      for (int i = 1; i < N; i++)
      {
        int northNorthCost = in.nextInt();
        int northSouthCost = in.nextInt();
        int southNorthCost = in.nextInt();
        int southSouthCost = in.nextInt();
        int newNorthCost = Math.min(northCost + northNorthCost, southCost + southNorthCost);
        int newSouthCost = Math.min(northCost + northSouthCost, southCost + southSouthCost);
        northCost = newNorthCost;
        southCost = newSouthCost;
      }
      
      int minimum = Math.min(northCost, southCost);
      System.out.println(minimum);
    }
    else if (assignment.trim().equals("Part 2"))
    {
      int N = in.nextInt();
      int M = in.nextInt();
      
      // board stores the costs of entering cities
      int[][] board = new int[N][];
      for (int i = 0; i < N; i++)
      {
        board[i] = new int[M];
        for (int j = 0; j < M; j++)
        {
          board[i][j] = in.nextInt();
        }
      }
      
      int[][] minimumCosts = new int[N][];
      minimumCosts[0] = new int[M];
      // The first row of cities you can only enter through the entrance
      for (int j = 0; j < M; j++)
      {
        minimumCosts[0][j] = board[0][j];
      }
      for (int i = 1; i < N; i++)
      {
        minimumCosts[i] = new int[M];
        // This determines the cheapest way to get to a city by foot (so without using the tunnels for this row)
        // Case 0 is the left side of the board, case M-1 is the right side.
        minimumCosts[i][0] = Math.min(minimumCosts[i-1][0], minimumCosts[i-1][1]) + board[i][0];
        for (int j = 1; j < M - 1; j++)
        {
          minimumCosts[i][j] = Math.min(minimumCosts[i-1][j-1],
                                        Math.min(minimumCosts[i-1][j], minimumCosts[i-1][j+1]))
                               + board[i][j];
        }
        minimumCosts[i][M - 1] = Math.min(minimumCosts[i-1][M - 2], minimumCosts[i-1][M - 1]) + board[i][M - 1];
        
        // Deal with the tunnels by simply checking whether its better to take a tunnel from a previous city
        int K = in.nextInt();
        for (int c = 0; c < K; c++)
        {
          int j = in.nextInt();
          int prevX = in.nextInt();
          int prevY = in.nextInt();
          int cost = in.nextInt();
          minimumCosts[i][j] = Math.min(minimumCosts[i][j], minimumCosts[prevX][prevY] + cost);
        }
      }
      // Find the best city to exit
      int result = minimumCosts[N-1][0];
      for (int j = 1; j < M; j++)
      {
        result = Math.min(result, minimumCosts[N-1][j]);
      }
      System.out.println(result);
    }
    else if (assignment.trim().equals("Part 3"))
    {
      int N = in.nextInt();
      int M = in.nextInt();
      
      int[] rooms = new int[N];
      rooms[0] = 0;
      for (int i = 1; i < N; i++)
      {
        // We use -1 as a special value, meaning 'not yet reached'
        rooms[i] = -1;
      }
      
      ArrayList<Integer>[] entrances = (ArrayList<Integer>[]) new ArrayList[N];
      ArrayList<Integer>[] costs = (ArrayList<Integer>[]) new ArrayList[N];
      for (int i = 0; i < N; i++)
      {
        entrances[i] = new ArrayList<Integer>();
        costs[i] = new ArrayList<Integer>();
      }
      // Add all portals to their exits
      for (int i = 0; i < M; i++)
      {
        int entr = in.nextInt();
        int exit = in.nextInt();
        int cost = in.nextInt();
        entrances[exit].add(entr);
        costs[exit].add(cost);
      }
      
      // For all rooms...
      for (int i = 0; i < N; i++)
      {
        // ...for all portals that exit here...
        for (int j = 0; j < entrances[i].size(); j++)
        {
          int entr = entrances[i].get(j);
          int cost = costs[i].get(j);
          // ...if the room is reachable...
          if (rooms[entr] != -1)
          {
            // ...figure out if the portals is a better way of reaching the room
            if (rooms[i] == -1)
            {
              rooms[i] = rooms[entr] + cost;
            }
            else
            {
              rooms[i] = Math.min(rooms[i], rooms[entr] + cost);
            }
          }
        }
      }
      
      System.out.println(rooms[N-1]);
    }
  }
}