Untitled

#include <iostream>
#include <stdio.h>
using namespace std;
int n, e, k, t;
float data[1001][1001];
float xx[1005][1005];

void kt() {
	for (int i = 0; i <= t; i++) {
		for (int j = 1; j <= n; j++) {
			xx[i][j] = 0;
		}
	}
	xx[0][1] = 1;

	for (int i = 1; i <= t; i++) {
		for (int ii = 1; ii <= n; ii++) {
			for (int jj = 1; jj <= n; jj++) {
			if (data[jj][ii] != 0 && xx[i-1][jj] != 0) {
				xx[i][ii] = xx[i][ii] + data[jj][ii] * xx[i-1][jj];
			}
			}
			
		}

	}

	

}

int main() {
	freopen("input.txt", "r", stdin);
	for (int stt = 1; stt <= 10; stt++) {
	    cin >> n >> e >> k >> t;
		int x, y;
		double z;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				data[i][j] = 0;
			}
		}

		for (int i = 0; i < e; i++) {
			cin >> x >> y >> z;
			data[x][y] = z;
		}
		int tk = t - k;
		t = t / 10;
		kt(); float maxx1=0;
		float maxx2 = 0;
        int vtri1=0, vtri2=0;
		for (int i = 1; i <= n; i++) {
			if (maxx1 < xx[t][i]) {
				maxx1 = xx[t][i];
				vtri1 = i;
			}
		}
		tk = tk/10;
		for (int i = 1; i <= n; i++) {
			if (maxx2 < xx[tk][i]) {
				maxx2 = xx[tk][i];
				vtri2 = i;
			}
		}
		//cout << vtri1<<" "<<maxx1<<" "<< vtri2<<" "<< maxx2<<endl;
		printf("#%d %d %.6f %d %.6f\n", stt, vtri1, maxx1, vtri2, maxx2);

		
	}
		return 0;
}