// Arup Guha
// 11/30/2015
// Solution to 2009 World Finals Problem E: Fare and Balanced

import java.util.*;
import java.io.*;

public class fare {

	final public static int NOPATH = 1000000000;

	public static int[] minDist;
	public static int[] maxDist;
	public static int n;
	public static edge[] roads;

	public static int[] minDFromEnd;
	public static int[] maxDFromEnd;

	public static ArrayList[] graph;
	public static ArrayList[] revGraph;

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		n = Integer.parseInt(tok.nextToken());
		int e = Integer.parseInt(tok.nextToken());
		int loop = 1;

		// Process each case.
		while (n != 0) {

			roads = new edge[e];

			// Read in graph.
			graph = new ArrayList[n];
			for (int i=0; i<n; i++)
				graph[i] = new ArrayList<edge>();

			// We also need edges stored in "reverse" order.
			revGraph = new ArrayList[n];
			for (int i=0; i<n; i++)
				revGraph[i] = new ArrayList<edge>();

			for (int i=0; i<e; i++) {
				tok = new StringTokenizer(stdin.readLine());
				int v1 = Integer.parseInt(tok.nextToken()) - 1;
				int v2 = Integer.parseInt(tok.nextToken()) - 1;
				int c = Integer.parseInt(tok.nextToken());
				roads[i] = new edge(v1, v2, c, i+1);
				graph[roads[i].v1].add(roads[i]);
				revGraph[roads[i].v2].add(roads[i]);
			}

			minDist = new int[n];
			maxDist = new int[n];
			minDFromEnd = new int[n];
			maxDFromEnd = new int[n];

			boolean res = solve();

			// Can't do it.
			if (!res)
				System.out.println("Case "+loop+": No solution");

			// Usual case.
			else {

				// Calculate number of roads to toll.
				int numToll = 0;
				for (edge x: roads)
					if (x.toll > 0)
						numToll++;

				// Output each road with a toll.
				StringBuffer sb = new StringBuffer();
				sb.append("Case "+loop+": "+numToll+" "+maxDist[n-1]+"\n");
				for (edge x: roads)
					if (x.toll > 0)
						sb.append(x.ID+" "+ x.toll+"\n");
				System.out.print(sb);
			}

			// Get next case.
			loop++;
			tok = new StringTokenizer(stdin.readLine());
			n = Integer.parseInt(tok.nextToken());
			e = Integer.parseInt(tok.nextToken());
		}
	}

	public static boolean solve() throws Exception {

		// Pre-compute shortest and longest distances, from both residential area and downtown.
		solveMinD(minDist, true);
		solveMaxD(maxDist, true);
		solveMinD(minDFromEnd, false);
		solveMaxD(maxDFromEnd, false);

		// Go through each road.
		for (int i=0; i<roads.length; i++) {

			int a = roads[i].v1;
			int b = roads[i].v2;
			if (minDist[a] == maxDist[a] && minDist[b] != maxDist[b] && maxDist[n-1] - maxDist[a] != roads[i].c + maxDFromEnd[b])
				roads[i].toll = maxDist[n-1] - maxDist[a] - (roads[i].c + maxDFromEnd[b]);

			// Means it's impossible since we could have a toll before and one after.
			if (minDist[a] != maxDist[a] && minDFromEnd[a] != maxDFromEnd[a])
				return false;
		}

		// We made it!
		return true;
	}

	// Solves for all min distances. If flag = true, source = residential, otherwise source = downtown.
	public static void solveMinD(int[] myMinDist, boolean flag) {
		Arrays.fill(myMinDist, NOPATH);
		int source = flag ? 0 : n-1;
		int dest = flag ? n-1 : 0;
		myMinDist[source] = 0;
		recMinD(myMinDist, dest, flag);
	}

	// Recursively finds the shortest distance from source to v. If flag = true, source = residential, otherwise downtown.
	public static int recMinD(int[] myMinDist, int v, boolean flag) {

		// We solved it already.
		if (myMinDist[v] != NOPATH) return myMinDist[v];

		// Tells us which graph to use.
		ArrayList[] g = flag ? revGraph : graph;
		int res = NOPATH;

		// Try all edges leaving v in the direction we seek.
		for (int i=0; i<g[v].size(); i++) {
			edge e = ((ArrayList<edge>)g[v]).get(i);
			int tmp = flag ? e.c + recMinD(myMinDist, e.v1, flag) : e.c + recMinD(myMinDist, e.v2, flag);
			res = Math.min(res, tmp);
		}

		// Store result and return.
		myMinDist[v] = res;
		return res;
	}

	// Solves for all max distances. If flag = true, source = residential, otherwise source = downtown.
	public static void solveMaxD(int[] myMaxDist, boolean flag) {
		Arrays.fill(myMaxDist, -1);
		int source = flag ? 0 : n-1;
		int dest = flag ? n-1 : 0;
		myMaxDist[source] = 0;
		recMaxD(myMaxDist, dest, flag);
	}

	// Recursively finds the longest distance from source to v. If flag = true, source = residential, otherwise downtown.
	public static int recMaxD(int[] myMaxDist, int v, boolean flag) {

		// We did this already.
		if (myMaxDist[v] != -1) return myMaxDist[v];

		// Tells us which graph to use.
		ArrayList[] g = flag ? revGraph : graph;
		int res = 0;

		// Try all edges from v in direction we want.
		for (int i=0; i<g[v].size(); i++) {
			edge e = ((ArrayList<edge>)g[v]).get(i);
			int tmp = flag ? e.c + recMaxD(myMaxDist, e.v1, flag) : e.c + recMaxD(myMaxDist, e.v2, flag);
			res = Math.max(res, tmp);
		}

		// Store answer and return.
		myMaxDist[v] = res;
		return res;
	}

}

class edge {

	public int v1;
	public int v2;
	public int c;
	public int ID;
	public int toll;

	public edge(int myv1, int myv2, int myc, int myID) {
		v1 = myv1;
		v2 = myv2;
		c = myc;
		ID = myID;
		toll = 0;
	}
}