Untitled

package test;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, k, j;
	static double[][] a = new double[305][305];
	static double[] vs = new double[305];
	static int[] vt = new int[305];
	static double res1, res2;
	static int idx1, idx2;
	public static void main(String[] args) throws FileNotFoundException {
		//Scanner sc = new Scanner(System.in);
		Scanner sc = new Scanner(new File("/home/toannv/bss/java/test/src/input.txt"));
		int T = 1;
		for(int t=1; t<=T; t++){
			n = sc.nextInt();
			m = sc.nextInt();
			k = sc.nextInt();
			j = sc.nextInt();
			k = j-k;
//			if(k%10==0){
//				k/=10+1;
//			}else{
//				k =k/10+1;
//			}
//			if(j%10==0){
//				j/=10+1;
//			}else{
//				j =j/10;
//			}
			
			for(int i=0; i<=n; i++) {
				vs[i]=0;
				for(int j=0; j<=n; j++) {
					a[i][j]=0;
				}
			}
			
			for(int i=0; i<m; i++){
				int xx = sc.nextInt();
				int yy = sc.nextInt();
				double dept = sc.nextDouble();
				a[xx][yy] = dept;
			}
			
			System.out.println(k+" "+j);
			
			for(int i=1; i<=n; i++){
				for(int j=1; j<=n; j++){
					System.out.print(a[i][j]+" ");
				}
				System.out.println();
			}
			idx1=0; idx2=0; res1=0; res2=0; 
			if(k<10) {
				idx1=1;
				res1=1;
			}
			if(j<10) {
				idx2=1;
				res2=1;
			}
			BFS();
//			System.out.println(idx1 + " " + res1 + " " + idx2 + " " + res2);
			System.out.format("#%d %d %.6f %d %.6f\n", t, idx2, res2, idx1, res1);
		}
	}

	static void BFS(){
		int[] q = new int[205];
		int l=0, r=0;
		q[r++]=1;
		vs[1]=1;
		vt[1]=0;
		int cnt=0;
		while(l<r){
			int top = q[l++];
			double vl = vs[top];
			int turn = vt[top]+10;
			if(turn==j+20) break;
			System.out.println("top" + top + " " + vl);
			
			double max = 0;
			int idx=-1;
			for(int i=1; i<=n; i++){
				if(a[top][i]>0){
					System.out.println(i+ " a top: "+a[top][i]);
					if(vt[i]==turn){
						vs[i] = vs[i] + vl*a[top][i];
					}else {
						vs[i] = vl*a[top][i];
						q[r++]=i;
					}
					vt[i]=turn;
					System.out.println("vs "+vs[i]);
					if(vs[i]>max){
						max=vs[i]; idx=i;
					}
					
				}
			}
			if(idx!=-1){
				System.out.println("turn: "+turn);
				if(k>=turn && k<turn+10) {
					if(max>res1) {
						res1 = max;
						idx1 = idx;
					}
				}
				if(j>=turn && j<turn+10) {
					if(max>res2) {
						res2 = max;
						idx2 = idx;
					}
				}
			}
			
			printVS();
			System.err.println(max+" "+idx);
		}
	}
	
	static void printVS(){
		System.out.println();
		for(int i=1; i<=n; i++){
			System.out.print(vs[i]+" ");
		}
		System.out.println();
	}
}