#include <perms.h>

//          Edinburgh IMP77 Compiler - Version 8.4
//
//     1  %begin

int main(int argc, char **argv) { /*%begin*/
  _imp_initialise(argc, argv);

  //     2      %integer n

  int N;

  //     3      %record %format flightfm(%integer from,to,cost)

  struct FLIGHTFM {
    union {
      struct {
        int FROM;
        int TO;
        int COST;
      };
    };
  };

  //     4
  //     5      %integer %function min(%integer a, b)

  int MIN(int A, int B) {
    //     6          %result = a %if (a < b)

    if (A >= B) goto L_0001;
    return A;
  L_0001:;

  //     7          %result = b

    return B;

    //     8      %end

  } /* end of MIN */

  //     9
  //    10      select input(1)

  _imp_SELECTINPUT(1);

  //    11      read(n)

  _imp_READ(/*?*/ &N);

  //    12
  //    13      %begin

  { /*%begin*/

    //    14          %record(flightfm) %array flights(1:n)

    struct FLIGHTFM FLIGHTS[N - 1 + 1];

    //    15          %integer i,start,destination,stops, min cost, max cost

    int I;
    int START;
    int DESTINATION;
    int STOPS;
    int MINCOST;
    int MAXCOST;

    //    16
    //    17          %routine cheapest price( %integer src, dst, stops, cost so far )

    void CHEAPESTPRICE(int SRC, int DST, int STOPS, int COSTSOFAR) {
      //    18              %integer i

      int I;

      //    19
      //    20              %if (src = dst) %start

      if (SRC != DST) goto L_0002;

        //    21                  min cost = min(min cost, cost so far)

      MINCOST = MIN(MINCOST, COSTSOFAR);

      //    22              %finish %else %if (stops >= 0) %start

      goto L_0003;
    L_0002:;
      if (STOPS < 0) goto L_0004;

        //    23
        //    24                  %for i = 1,1,n %cycle

        // %for I = 1, 1, N %cycle
      {
        int _final = N;
        if (invalid_for_loop(1, 1, _final)) _imp_signal(5, 1, 0, "Illegal cycle I = 1, 1, N");
        I = 0;
      L_0005:
        if (I == _final) goto L_0006;
        I += 1;

        //    25                      %if (flights(i)_from = src) %start

        if (FLIGHTS[I - 1].FROM != SRC) goto L_0008;

          //    26                          cheapest price( flights(i)_to, dst, stops - 1, cost so far + flights(i)_cost )

        CHEAPESTPRICE(FLIGHTS[I - 1].TO, DST, STOPS - 1, COSTSOFAR + FLIGHTS[I - 1].COST);

        //    27                      %finish

      L_0008:;

      //    28                  %repeat

        goto L_0005;
      }

    L_0006:;

    //    29
    //    30              %finish

    L_0004:;
    L_0003:;

    //    31
    //    32          %end

      return;
    } /* end of CHEAPESTPRICE */

    //    33
    //    34          %for i=1,1,n %cycle

    // %for I = 1, 1, N %cycle
    {
      int _final = N;
      if (invalid_for_loop(1, 1, _final)) _imp_signal(5, 1, 0, "Illegal cycle I = 1, 1, N");
      I = 0;
    L_0009:
      if (I == _final) goto L_000A;
      I += 1;

      //    35              read(flights(i)_from)

      _imp_READ(/*?*/ &FLIGHTS[I - 1].FROM);

      //    36              read(flights(i)_to)

      _imp_READ(/*?*/ &FLIGHTS[I - 1].TO);

      //    37              read(flights(i)_cost)

      _imp_READ(/*?*/ &FLIGHTS[I - 1].COST);

      //    38          %repeat

      goto L_0009;
    }

  L_000A:;

  //    39          read(start)

    _imp_READ(/*?*/ &START);

    //    40          read(destination)

    _imp_READ(/*?*/ &DESTINATION);

    //    41          read(stops)

    _imp_READ(/*?*/ &STOPS);

    //    42
    //    43          select output(0)

    _imp_SELECTOUTPUT(0);

    //    44          %for i=1,1,n %cycle

    // %for I = 1, 1, N %cycle
    {
      int _final = N;
      if (invalid_for_loop(1, 1, _final)) _imp_signal(5, 1, 0, "Illegal cycle I = 1, 1, N");
      I = 0;
    L_000C:
      if (I == _final) goto L_000D;
      I += 1;

      //    45              print string("Flight(".itos(i,0)."): ");

      _imp_PRINTSTRING(
          *({
            __typeof__(_imp_string255) tmp = *({
              _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ &*({
                                               _imp_string255 tmp =
                                                   _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("Flight("), ({
                                                               __typeof__(_imp_string255) tmp; /*E*/
                                                               tmp = _imp_ITOS(I, 0);
                                                               (void *)&tmp;
                                                             }));
                                               (_imp_string255 *)&tmp;
                                             }),
                                             (_imp_string *)/*?*/ _imp_str_literal_ptr("): "));
              (_imp_string255 *)&tmp;
            }) /*q*/;
            (_imp_string255 *)&tmp;
          })
      );

      //    46              print string(" From: ".itos(flights(i)_from,0))

      _imp_PRINTSTRING(
          *({
            __typeof__(_imp_string255) tmp = *({
              _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr(" From: "), ({
                                               __typeof__(_imp_string255) tmp; /*E*/
                                               tmp = _imp_ITOS(FLIGHTS[I - 1].FROM, 0);
                                               (void *)&tmp;
                                             }));
              (_imp_string255 *)&tmp;
            }) /*q*/;
            (_imp_string255 *)&tmp;
          })
      );

      //    47              print string("   To: ".itos(flights(i)_to,0))

      _imp_PRINTSTRING(
          *({
            __typeof__(_imp_string255) tmp = *({
              _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("   To: "), ({
                                               __typeof__(_imp_string255) tmp; /*E*/
                                               tmp = _imp_ITOS(FLIGHTS[I - 1].TO, 0);
                                               (void *)&tmp;
                                             }));
              (_imp_string255 *)&tmp;
            }) /*q*/;
            (_imp_string255 *)&tmp;
          })
      );

      //    48              print string(" Cost: ".itos(flights(i)_cost,0))

      _imp_PRINTSTRING(
          *({
            __typeof__(_imp_string255) tmp = *({
              _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr(" Cost: "), ({
                                               __typeof__(_imp_string255) tmp; /*E*/
                                               tmp = _imp_ITOS(FLIGHTS[I - 1].COST, 0);
                                               (void *)&tmp;
                                             }));
              (_imp_string255 *)&tmp;
            }) /*q*/;
            (_imp_string255 *)&tmp;
          })
      );

      //    49              newline

      _imp_NEWLINE();

      //    50          %repeat

      goto L_000C;
    }

  L_000D:;

  //    51          printstring("      Start: ".itos(start,0)); newline

    _imp_PRINTSTRING(
        *({
          __typeof__(_imp_string255) tmp = *({
            _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("      Start: "), ({
                                             __typeof__(_imp_string255) tmp; /*E*/
                                             tmp = _imp_ITOS(START, 0);
                                             (void *)&tmp;
                                           }));
            (_imp_string255 *)&tmp;
          }) /*q*/;
          (_imp_string255 *)&tmp;
        })
    );
    _imp_NEWLINE();

    //    52          printstring("Destination: ".itos(destination,0)); newline

    _imp_PRINTSTRING(
        *({
          __typeof__(_imp_string255) tmp = *({
            _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("Destination: "), ({
                                             __typeof__(_imp_string255) tmp; /*E*/
                                             tmp = _imp_ITOS(DESTINATION, 0);
                                             (void *)&tmp;
                                           }));
            (_imp_string255 *)&tmp;
          }) /*q*/;
          (_imp_string255 *)&tmp;
        })
    );
    _imp_NEWLINE();

    //    53          printstring("      Stops: ".itos(stops,0)); newline

    _imp_PRINTSTRING(
        *({
          __typeof__(_imp_string255) tmp = *({
            _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("      Stops: "), ({
                                             __typeof__(_imp_string255) tmp; /*E*/
                                             tmp = _imp_ITOS(STOPS, 0);
                                             (void *)&tmp;
                                           }));
            (_imp_string255 *)&tmp;
          }) /*q*/;
          (_imp_string255 *)&tmp;
        })
    );
    _imp_NEWLINE();

    //    54          max cost = 0

    MAXCOST = 0;

    //    55          %for i = 1,1,n %cycle

    // %for I = 1, 1, N %cycle
    {
      int _final = N;
      if (invalid_for_loop(1, 1, _final)) _imp_signal(5, 1, 0, "Illegal cycle I = 1, 1, N");
      I = 0;
    L_000E:
      if (I == _final) goto L_000F;
      I += 1;

      //    56              max cost = max cost + flights(i)_cost

      MAXCOST = MAXCOST + FLIGHTS[I - 1].COST;

      //    57          %repeat

      goto L_000E;
    }

  L_000F:;

  //    58          print string( "Greatest cost: ".itos(max cost,0));newline

    _imp_PRINTSTRING(
        *({
          __typeof__(_imp_string255) tmp = *({
            _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("Greatest cost: "), ({
                                             __typeof__(_imp_string255) tmp; /*E*/
                                             tmp = _imp_ITOS(MAXCOST, 0);
                                             (void *)&tmp;
                                           }));
            (_imp_string255 *)&tmp;
          }) /*q*/;
          (_imp_string255 *)&tmp;
        })
    );
    _imp_NEWLINE();

    //    59
    //    60          min cost = max cost

    MINCOST = MAXCOST;

    //    61          cheapest price( start, destination, stops, 0 )

    CHEAPESTPRICE(START, DESTINATION, STOPS, 0);

    //    62          %if (min cost = max cost) %start

    if (MINCOST != MAXCOST) goto L_0010;

      //    63              print string( "No route found for #hops, start, end points and the given flights data")

    _imp_PRINTSTRING(_imp_str_literal("No route found for #hops, start, end points and the given flights data"));

    //    64          %finish %else %start

    goto L_0011;
  L_0010:;

  //    65              print string( "Minimum cost: ".itos(min cost,0))

    _imp_PRINTSTRING(
        *({
          __typeof__(_imp_string255) tmp = *({
            _imp_string255 tmp = _imp_join((_imp_string *)/*?*/ _imp_str_literal_ptr("Minimum cost: "), ({
                                             __typeof__(_imp_string255) tmp; /*E*/
                                             tmp = _imp_ITOS(MINCOST, 0);
                                             (void *)&tmp;
                                           }));
            (_imp_string255 *)&tmp;
          }) /*q*/;
          (_imp_string255 *)&tmp;
        })
    );

    //    66          %finish

  L_0011:;

  //    67          newline

    _imp_NEWLINE();

    //    68
    //    69      %end

    goto end_1000;
  end_1000:;
  }

  //    70
  //    71  %end

  _imp_stop(0);
  return 0;
end_0:;
}

//    72  %endoffile