Untitled

package Visit_Department;

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
	static int n, m, k, w;
	static int[][] a;
	static float[][] c;
	static float[][] mt;
	
	public static void main(String args[]) throws Exception{
		System.setIn(new FileInputStream("src/Visit_Department/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		int Answer;
		T=10;
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			m = sc.nextInt();
			k = sc.nextInt();
			w = sc.nextInt();
			k = w-k;
			w = w/10;
			k = k/10;
			a = new int[n+5][n+5];
			c = new float[n+5][n+5];
			mt = new float[n+5][w+5];
			
			for(int i = 0; i < m; i++){
				int p = sc.nextInt();
				int e = sc.nextInt();
				a[p][e] = 1;
				c[p][e] = sc.nextFloat();
			}
			
			mt[1][0] = 1;
			
			for(int u = 1; u <= w; u++){
				for(int i = 0; i <= n; i++){
					if(mt[i][u-1] != 0){
						for(int j = 1; j <= n; j++){
							if(a[i][j] == 1){
								mt[j][u] += mt[i][u-1]*c[i][j];
							}
						}
					}
				}
			}
			
			float max1 = -1;
			int td1 = -1;
			for(int i = 0; i <= n; i++){
				if(max1 < mt[i][w]){
					max1 = mt[i][w];
					td1 = i;
				}
			}
			
			float max2 = -1;
			int td2 = -1;
			for(int i = 0; i <= n; i++){
				if(max2 < mt[i][k]){
					max2 = mt[i][k];
					td2 = i;
				}
			}
			
			System.out.print("#" + test_case + " ");
			System.out.print(td1 + " ");
			System.out.format("%.6f ", max1);
			System.out.print(td2 + " ");
			System.out.format("%.6f", max2);
			System.out.println();
		}
	}
}