Untitled

//Minimal Big Sum
#include <iostream>
using namespace std;
int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		int k, n;
		cin >> k >> n;
		int arr[100005];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		while (true) {
			int sum = 0;
			int count = 1;

			for (int i = 0; i < n; i++) {
				sum += arr[i];
				if (sum > max) {
					count++;
					sum = arr[i];
				}
			}
			if (count <= k)
				break;
			max++;
		}
		cout << "# " << tc << " " << max << endl;
	}
}

//Stack
#include <iostream>
using namespace std;

int arr[1000];
int size_stack;

void push(int num) {
	arr[size_stack] = num;
	size_stack++;
}

void pop() {
	size_stack--;
}

bool empty() {
	if (size_stack <= 0)
		return true;
	return false;
}

int top() {
	return arr[size_stack-1];
}

int getSize() {
	return size_stack;
}

//Queue
#include <iostream>
using namespace std;

int arr[100];
int size_queue;

void push(int num) {
	arr[size_queue] = num;
	size_queue++;
}

int front() {
	return arr[0];
}

void pop() {
	for (int i = 0; i < size_queue; i++) {
		int temp = arr[i];
		arr[i] = arr[i + 1];
		arr[i + 1] = temp;
	}
	size_queue--;
}

int getSize() {
	return size_queue;
}

bool empty() {
	if (size_queue <= 0)
		return true;
	return false;
}

// Sort
#include <iostream>
using namespace std;

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void quick_sort(int arr[1000], int l, int r) {
	int i = l, j = r;
	int tg = arr[(l + r) / 2];
	while (i <= j) {
		while (arr[i] < tg) {
			i++;
		}
		while (arr[j] > tg) {
			j--;
		}
		if (i <= j) {
			swap(arr[i], arr[j]);
			i++;
			j--;
		}
	}
	if (l < j) {
		quick_sort(arr, l, j);
	}
	if (i < r) {
		quick_sort(arr, i, r);
	}
}

void merge(int arr[1000], int l, int m, int r) {
	int n1 = m - l + 1;
	int n2 = r - m;
	int L[1000], R[1000];

	for (int i = 0; i < n1; i++) {
		L[i] = arr[l + i];
	}

	for (int j = 0; j < n2; j++) {
		R[j] = arr[m + j + 1];
	}

	int i = 0, j = 0, k = l;

	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}

	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

void merge_sort(int arr[1000], int l, int r) {
	if (l < r) {
		int m = (l + r) / 2;
		
		merge_sort(arr, l, m);
		merge_sort(arr, m + 1, r);

		merge(arr, l, m, r);
	}
}


int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		int n;
		cin >> n;
		int arr[1000];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		merge_sort(arr, 0, n - 1);
		//quick_sort(arr, 0, n - 1);

		cout << "Case #" << tc << endl;

		for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
		}

		cout << endl;
	}
}

// DFS
#include <iostream>
using namespace std;

int n;
int arr[30000][30000];
int dd[50005], b[5005], c[5005];
int dem, dem2;
int len, len2;
int kc[50005];

void DFS(int i, int v) {
	dd[i] = 1;
	if (i == v) {
		if (len > len2) {
			len2 = len;
			kc[v] = len2;
		}
	}
	else {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != 0 && dd[j] == 0) {
				len += arr[i][j];
				dd[j] = 1;
				DFS(j, v);
				dd[j] = 0;
				len -= arr[i][j];
			}
		}
	}
}

void DFS2(int i) {
	dd[i] = 1;
	if (len > len2) {
		len2 = len;
	}
	for (int j = 1; j <= n; j++) {
		if (arr[i][j] != 0 && dd[j] == 0) {
			len += arr[i][j];
			dd[j] = 1;
			DFS2(j);
			dd[j] = 0;
			len -= arr[i][j];
		}
	}
}

int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cin >> n;

		for (int i = 0; i < n - 1; i++) {
			int x, y, z;
			cin >> x >> y >> z;
			arr[x][y] = z;
			arr[y][x] = z;
		}

		int u = 1;
		for (int j = 1; j <= n; j++) {
			dd[u] = 1;
			len = 0, len2 = 0;
			DFS(u, j);
		}

		int max = 0;
		int temp = 0;
		for (int i = 1; i <= n; i++) {
			if (kc[i] > max) {
				max = kc[i];
				temp = i;
			}
		}
		for (int i = 0; i < 50005; i++) {
			dd[i] = 0;
		}
		dd[temp] = 1;
		len = 0, len2 = 0;
		DFS2(temp);
		cout << len2 << endl;
	}
}