/*
 * example implementation for dijkstra's
 */

#include <iostream>
#include <iomanip>
#include <queue>
#include <list>
#include <string>

using namespace std;

struct adj_struct {
	struct vertex_struct *e;
	int weight;
};

struct vertex_struct {
	int num;
	unsigned long int spath;
	list<struct adj_struct *> adj;
};


void
update (int n1, int n2, int w);

struct vertex_struct *
fn (int num);

int
spath (int s, int e);

void
resetw (void);

list<struct vertex_struct *> vlist;

#define BIG 40000000
int
main (void)
{
	char s [100], *ptr;
	int n1, n2, w;

	strcpy (s, "f");

	while (cin.getline (s, 100) && strcmp (s, "$END")) {
		ptr = strtok (s, " ");
		n1 = atoi (ptr);
		ptr = strtok (NULL, " ");
		n2 = atoi (ptr);
		ptr = strtok (NULL, " ");
		w = atoi (ptr);

		update (n1, n2, w);
	}

#if 0
	cout << "vlist: " << endl;

	for (list<struct vertex_struct *>::iterator i = vlist.begin ();
	     i != vlist.end (); i++) {
		cout << "   " << (*i) -> num << ": ";
		
		for (list<struct adj_struct *>::iterator j = (*i)->adj.begin();
		     j != (*i)->adj.end (); j++) {
			cout << (*j) -> e -> num << "(" 
			     << (*j) -> weight << ") ";
		}

		cout << endl;
	}

	cout << "Read graph" << endl;
#endif

	while (cin.getline (s, 100)) {
		ptr = strtok (s, " ");
		n1 = atoi (ptr);
		ptr = strtok (NULL, " ");
		n2 = atoi (ptr);
		
		w = spath (n1, n2);

		cout << n1 << " to " << n2 << ": ";

		if (w < 0)
			cout << "No Path" << endl;
		else
			cout << w << endl;
	}

	return 0;
}


void
update (int n1, int n2, int w)
{
	struct vertex_struct *v1, *v2;
	struct adj_struct *adj;


	v1 = fn (n1);
	v2 = fn (n2);

	adj = new struct adj_struct;
	adj -> weight = w;
	adj -> e = v2;

	list<adj_struct *>::iterator i = v1 -> adj.begin ();

	for ( ; i != v1 -> adj.end (); i++) {
		if ((*i) -> e -> num > adj -> e -> num)
			break;
	}

	if (v1 -> adj.empty ())
		v1 -> adj.push_front (adj);
	else if (i == v1 -> adj.end ()) {
		if (v1 -> adj.back () -> e -> num < adj -> e -> num)
			v1 -> adj.push_back (adj);
		else
			v1 -> adj.insert (i, adj);
	}
	else
		v1 -> adj.insert (i, adj);
}

struct vertex_struct *
fn (int num)
{
	struct vertex_struct *item;
	list<struct vertex_struct *>::iterator  it = vlist.begin ();

	item = NULL;

	for ( ; it != vlist.end (); it++) {
		if ((*it) -> num == num) {
			item = *it;
			break;
		}
		else if ((*it)  -> num > num) {
			break;
		}
	}

	if (!item) {
		item = new struct vertex_struct;
		item -> num = num;

		if (vlist.empty ())
			vlist.push_front (item);
		else if (it == vlist.end ()) {
			if (vlist.back () -> num < num)
				vlist.push_back (item);
			else
				vlist.insert (it, item);
		}
		else
			vlist.insert (it, item);
	}

	return item;
}


int
spath (int s, int e)
{
	list<struct vertex_struct *>work;
	struct vertex_struct *cur;
	unsigned long int spath;

	resetw ();
	cur = fn (s);
	cur -> spath = 0;
	work.push_front (cur);

	while (!work.empty ()) {
		cur = work.front ();
		work.pop_front ();

		for (list<struct adj_struct *>::iterator i = cur ->adj.begin();
		     i != cur -> adj.end (); i++) {
			spath = cur -> spath + (*i) -> weight;

			if (spath < (*i) -> e -> spath) {
				(*i) -> e -> spath = spath;
				work.push_back ((*i) -> e);
			}
		}
	}

	cur = fn (e);
	
	if (cur -> spath == BIG)
		return -1;
	else
		return cur -> spath;
}


void
resetw (void)
{
	list<struct vertex_struct *>::iterator i = vlist.begin ();
	
	for ( ; i != vlist.end (); i++) {
		(*i) -> spath = BIG;
	}
}