var line, data = [], i = -1, s, e, arr = [], arr2 = [];

while(line = read_line()){

      line = line.split(' ');

      if(i == -1){

            s = parseInt(line[0]);

            e = parseInt(line[1]);

      }

      else{

            data[i] = [parseInt(line[0]), parseInt(line[1]), parseInt(line[2])];

      }

      i++;

}

function findNext(start, con, his){

      if(start == e){

            arr.push(con);

            arr2.push(his + '->1050');

            return con;

      }

      for(var n = 0, max = data.length; n < max; n++){

            if(data[n][0] == start){

                  findNext(data[n][1], con + data[n][2], his + '->' + data[n][0]);

            }

      }

}

for(var n = 0, max = data.length; n < max; n++){

      if(data[n][0] == s){

            findNext(data[n][1], data[n][2], '1000');

      }

}

var min = arr[0], pos;

for(var n = 1; n < arr.length; n++){

      if(arr[n] < min){

            min = arr[n];

            pos = n;

      }

}

var str = arr2[pos] + '(' + min + ')';

print(str);