/**
 * Smp Version of Dijkstra's Algorithm
 */

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Scanner;
import edu.rit.pj.*;

public class DijkstraMatSmp {

	final static Integer infinity = 2000;
	static int[] distFromSource;
	static int[] previousNode;
	static int[] unvisitedNodes;
	static int[][] graph = null;
	static int len = 0;

	/**
	 * @param args
	 *            0 - Filename where Vertices and Edges are stored
	 * @param args
	 *            1 - Name of the source vertex
	 * @param args
	 *            2 - Name of the destination vertex
	 */
	public static void main( String[] args ) throws Exception {
		long time = -System.currentTimeMillis();
		Comm.init( args );
		String fileName = null;
		int source = 0;
		int destination = 0;
		if (args.length == 3) {
			fileName = args[0];
			source = Integer.parseInt(args[1]);
			destination = Integer.parseInt(args[2]);
		} else {
			System.err.println("Invalid command-line arguements");
			System.exit(0);
		}

		try {
			BufferedReader in = new BufferedReader(new FileReader(fileName));
			String line = in.readLine();
			len = Integer.parseInt( line );
			graph = new int[len][len];
			for( int a = 0; a < len; a++ ) {
				for( int b = 0; b < len; b++ ) {
					graph[a][b] = infinity;
				}
			}
			while ((line = in.readLine()) != null) {
				Scanner scan = new Scanner( line );
				int pointA = scan.nextInt();
				int pointB = scan.nextInt();
				int dist = scan.nextInt();
				graph[pointA][pointB] = dist;
				graph[pointB][pointA] = dist;
			}
			in.close();
		} catch( Exception e ) {
			e.printStackTrace();
		}
		
		//*** Dijkstra's Algorithm ***\\
		distFromSource = new int[len];
		previousNode = new int[len];
		unvisitedNodes = new int[len];
		for( int i = 0; i < len; i++ ) {
			distFromSource[i] = infinity;
			previousNode[i] = -1;
		}
		distFromSource[source] = 0;
		
		new ParallelTeam().execute( new ParallelRegion() 
			{
				public void run() throws Exception {
					execute( 0, len-1, new IntegerForLoop()
						{
							public void run (int first, int last) {
								for( int j = first; j <= last; j++ ) {
									int currentNode = j;
									for( int j2 = 0; j2 < len; j2++ ) {
										if( distFromSource[j2] < distFromSource[currentNode] && unvisitedNodes[j2] != 1 )
											currentNode = j2;
									}
									unvisitedNodes[currentNode] = 1;
									for( int k = j; k < graph[currentNode].length; k++ ) {
										int newDist = distFromSource[currentNode] + graph[currentNode][k];
										if( newDist < distFromSource[k] ) {
											distFromSource[k] = newDist;
											previousNode[k] = currentNode;
										}
									}
								}
							}
						});
				}
			});
		
		//Print out the output
		int prev = previousNode[destination];
		String output = "[" + destination + "]";
		while( source != prev ) {
			output = "[" + prev + "] -> " + output;
			prev = previousNode[prev];
		}
		output = "[" + source + "] -> " + output + " (Total Distance = " + distFromSource[destination] + ")";
		System.out.println( output );
		System.out.println( "Running Time : " + (System.currentTimeMillis() + time) );
	}

}