// Arup Guha
// 3/12/2019
// Solution to 2019 UCF HS Contest Problem: Life Decisions

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

public class life {

	// Stores data about original graph.
	public static int n;
	public static ArrayList[] out;
	public static int e;
	public static int[] loc;
	public static int[] weights;
	
	// For run time...
	public static int[] memo;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int numCases = Integer.parseInt(stdin.readLine().trim());
		
		// Process each case.
		for (int loop=1; loop<=numCases; loop++) {
			
			// Set up basic graph.
			StringTokenizer tok = new StringTokenizer(stdin.readLine());
			n = Integer.parseInt(tok.nextToken());
			e = Integer.parseInt(tok.nextToken());
			out = new ArrayList[n];
			for (int i=0; i<n; i++) out[i] = new ArrayList<edge>();
			loc = new int[e];
			weights = new int[e];
			
			// Get the edges and add to our original graph.
			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 w = Integer.parseInt(tok.nextToken());
				out[v1].add(new edge(v2, w, i));
				loc[i] = v2;
				weights[i] = w;
			}
			
			// Sort so we know when to stop looking for outgoing edges from a previous edge.
			for (int i=0; i<n; i++) Collections.sort(out[i]);
			
			// Solve and output result.
			System.out.println("Scenario #"+loop+": "+wrapper());
		}
	}
	
	public static int wrapper() {
		
		// Try each possible starting edge, and take best answer.
		int res = 0;
		memo = new int[e];
		Arrays.fill(memo, -1);
		for (edge e: (ArrayList<edge>)out[0])
			res = Math.max(res, go(e.id));
		
		// Ta da!
		return out[0].size() == 0 ? res : res+1;
	}
	
	// Gets the best answer from this edge.
	public static int go(int edgeid) {
		
		// Did this before.
		if (memo[edgeid] != -1) return memo[edgeid];
		
		ArrayList<edge> nextList = (ArrayList<edge>)out[loc[edgeid]];
		
		int res = 0;
		
		// Try each outgoing edge.
		for (int i=0; i<nextList.size(); i++) {
			
			// Values have gotten too small.
			if (Math.abs(weights[edgeid]) >= Math.abs(nextList.get(i).w)) break;
			
			// Can't go neg to pos.
			if (weights[edgeid] < 0 && nextList.get(i).w > 0) continue;
			
			// Try this...
			res = Math.max(res, go(nextList.get(i).id)+1);
		}
		
		// Store and return.
		return memo[edgeid] = res;
	}

}

class edge implements Comparable<edge> {
	
	public int v;
	public int w;
	public int id;
	
	public edge(int myv, int myw, int myid) {
		v = myv;
		w = myw;
		id = myid;
	}
	
	public int compareTo(edge other) {
		return Math.abs(other.w) - Math.abs(w); 
	}
}