/*
#include <stdio.h>
#include <stdlib.h>
// 2607. 쌍둥이 소수
int main() {
int a, b, i, j, prevPrime;
int *isComposite;
scanf("%d %d", &a, &b);
isComposite = calloc(b + 1, sizeof(int));
for (i = 2; i < a; i++) {
if (isComposite[i]) {
continue;
}
for (j = i * 2; j <= b; j += i) {
isComposite[j] = 1;
}
}
prevPrime = -1;
for (i = a; i <= b; i++) {
if (isComposite[i]) {
continue;
}
if (i - prevPrime == 2) {
printf("%d %d\n", prevPrime, i);
}
prevPrime = i;
for (j = i * 2; j <= b; j += i) {
isComposite[j] = 1;
}
}
free(isComposite);
return 0;
}
*/
/*
#include <stdio.h>
// 3009. 부분수열의 합
int main() {
int n, s, i, j, sum, temp, numberOfCases;
int numbers[20] = {0};
scanf("%d\n%d", &n, &s);
for (i = 0; i < n; i++) {
scanf("%d", &numbers[i]);
}
numberOfCases = 0;
for (i = 1; i < (1 << n); i++) {
temp = i;
sum = 0;
for (j = 0; temp > 0; j++) {
if (temp % 2 == 1) {
sum += numbers[j];
}
temp /= 2;
}
if (sum == s) {
numberOfCases++;
}
}
printf("%d", numberOfCases);
return 0;
}
*/
/*
#include <stdio.h>
int main() {
int m, n, i, j, result, temp, numberOfCases;
int numbers[20] = {0};
scanf("%d\n%d", &m, &n);
for (i = 0; i < n; i++) {
scanf("%d", &numbers[i]);
}
numberOfCases = 0;
for (i = 0; i < (1 << n); i++) {
temp = i;
result = 0;
for (j = 0; j < n; j++) {
if (temp % 2 == 1) {
result -= numbers[j];
} else {
result += numbers[j];
}
temp /= 2;
}
if (result == m) {
numberOfCases++;
}
}
printf("%d", numberOfCases);
return 0;
}
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int main() {
int p, i, j, node1, node2, currentNode, nextNode, nextNodeDistance, nearestNode, nearestNodeDistance;
int visited[52] = {0};
int minDistances[52] = {0};
char c1, c2;
int paths[52][52] = {0};
scanf("%d", &p);
for (i = 0; i < p; i++) {
scanf("\n%c %c", &c1, &c2);
node1 = (c1 <= 'Z') * 26 + (c1 - 'A') % 32;
node2 = (c2 <= 'Z') * 26 + (c2 - 'A') % 32;
if (c1 == c2) {
scanf("%*d");
} else {
scanf("%d", &paths[node1][node2]);
paths[node2][node1] = paths[node1][node2];
}
}
currentNode = 51;
for (i = 0; i < 51; i++) {
minDistances[i] = INT_MAX;
}
while (1) {
visited[currentNode] = 1;
nextNode = 0;
nextNodeDistance = INT_MAX;
for (j = 0; j < 51; j++) {
if (!visited[j]) {
if (paths[currentNode][j] > 0 &&
minDistances[currentNode] + paths[currentNode][j] < minDistances[j]) {
minDistances[j] = minDistances[currentNode] + paths[currentNode][j];
}
if (minDistances[j] < nextNodeDistance && minDistances[j] > 0) {
nextNode = j;
nextNodeDistance = minDistances[j];
}
}
}
if (nextNode == 0) {
break;
}
currentNode = nextNode;
}
nearestNode = 0;
nearestNodeDistance = INT_MAX;
for (i = 26; i < 51; i++) {
if (minDistances[i] < nearestNodeDistance) {
nearestNode = i;
nearestNodeDistance = minDistances[i];
}
}
printf("%c %d", nearestNode - 26 + 'A', nearestNodeDistance);
return 0;
}
/*
#include <stdio.h>
#include <stdlib.h>
// 2768. K-피보나치 수열 (Large)
int main() {
int k, n, i;
int sum = 0;
int *numbers;
scanf("%d %d", &k, &n);
numbers = calloc(n, sizeof(int));
for (i = 0; i < k; i++) {
scanf("%d", &numbers[i]);
numbers[i] %= 100007;
sum += numbers[i];
}
for (i = k; i < n; i++) {
numbers[i] = sum;
sum = (sum * 2 + 100007 - numbers[i - k]) % 100007;
}
printf("%d", numbers[n - 1]);
free(numbers);
return 0;
}
*/