import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Scanner;
import java.util.LinkedList;

public class AStar
{


	/**
	 * This class represents a state in your search space.
	 * It should contain whatever you need to track for the problem
	 */
	public class State implements Comparable<State>
	{

		/* problem specific variables */
		int node;
		LinkedList<Integer> path;
		double cost;

		/* Constructor should contain anything you need */
		public State(int curr, LinkedList<Integer> prev_path, double new_cost) //Add Params as needed
		{
			node=curr;
			path=new LinkedList<Integer>();
			path.addAll(prev_path);
			path.add(curr);
			cost=new_cost;
			//Add things as needed
		}


		/**
		 * Return the cost thus far to reach this state
		 */
		double getCost()
		{
			return cost;
		}

		/**
		 * Return the heurisitc value
		 *
		 * The heuristic is an estimate of how much cost
		 * it will take to go from here to the goal state.
		 *
		 * If you don't wish to write one, you can simply return 0
		 * to not use a heurisitc.  A heurisitc just speeds up the finding
		 * of the correct path.
		 *
		 * This must be an underestimate or exactly correct or the algorithm's
		 * result might not be optimal.
		 *
		 * Must also avoid triangle inequality problem, but that is rare.
		 *
		 *
		 */
		double getHeur()
		{
			return 0.0;
		}

		/** returns the total cost to reach goal.
		 *
		 * This is cost thus far plus the heurisitc estimate 
		 */
		double getEstimate()
		{
			return getCost() + getHeur();
		}


		/**
		 * Add the next states the priority queue (Q).
		 *
		 * The states should have updated costs and whatever other
		 * data needs to be tracked.
		 *
		 * Don't worry about duplicates, the search function handles those
		 */
		void next(PriorityQueue<State> Q)
		{
			//Add next hops from this state to queue Q
			//
			for(int i=0; i<numNodes; i++)
			{
				if (edges[node][i]!=0.0)
				{
					double new_cost=cost + edges[node][i];
					State new_state=new State(i,path,new_cost);
					Q.add(new_state);
				}

			}

		}

		/** returns true iff this is the goal state */
		boolean isGoal()
		{
			return (node==goalNode);
		}

		/** sorts by estimated cost (lowest cost first) 
		 * 
		 * using this the priority queue will be able to expand the lowest cost estimate
		 * elements first.
		 * */
		public int compareTo(State O)
		{
			double z=getEstimate();
			double oz=O.getEstimate();

			if (z < oz) return -1;
			if (z > oz) return 1;

			return 0;
			
		}


		/**
		 * returns a string that has the needed unique data for this state
		 *  
		 *  Used for the state visited list.  If two states return the same string,
		 *  they are assumed to represent the same state and only the lowest cost
		 *  of these will be considered.
		 *
		 *  This avoids expanding
		 */
		public String toString()
		{
			return "" + node;

		}


	}


	/**
	 * This is the actual search.
	 * None of the code here should need to be changed.
	 */
	public State search(State start_state)
	{
		PriorityQueue<State> Q=new PriorityQueue<State>();

		Q.add(start_state);

		HashSet<String> visited=new HashSet<String>(4096,0.5f);

		while(Q.peek()!=null)
		{
			State s=Q.poll();

			if (s.isGoal()) return s;

			String str=s.toString();
			if (!visited.contains(str))
			{
				visited.add(str);

				s.next(Q);

			}
		}
		return null;

	}

	//What follows is all problem specific

	public static void main(String Args[])
	{
		new AStar();
	}


	int startNode;
	int goalNode;
	int numNodes;

	double edges[][];
	

	public AStar()
	{
		Scanner in=new Scanner(System.in);

		while(true)
		{
			numNodes=in.nextInt();
			if (numNodes==0) return;
			startNode=in.nextInt();
			goalNode=in.nextInt();

			edges=new double[numNodes][numNodes];

			int edgecount=in.nextInt();
			for(int i=0; i<edgecount; i++)
			{
				int a=in.nextInt();
				int b=in.nextInt();
				double c=in.nextDouble();

				edges[a][b]=c;
				edges[b][a]=c;

			}

			State start=new State(startNode,new LinkedList<Integer>(),0.0);

			State answer=search(start);
			if (answer==null) System.out.println("No path");
			else System.out.println("path = " + answer.path + " cost = " + answer.getCost());

		}


	}

}