#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 52;
int dis[MAXN], adj[MAXN][MAXN], notvis[MAXN], n = MAXN;

void dijkstra(int src) {
    int sz = n;
    for (int i = 0; i < n; i++) dis[i] = 1e9;
    dis[src] = 0;
    int nxt = src;
    iota(begin(notvis), end(notvis), 0);
    while (nxt != -1) {
        int u = notvis[nxt];
        notvis[nxt] = notvis[--sz];
        nxt = -1;
        int best = 1e9;
        for (int i = 0; i < sz; i++) {
            int v = notvis[i];
            if (dis[v] > dis[u] + adj[u][v]) dis[v] = dis[u] + adj[u][v];
            if (dis[v] < best) best = dis[v], nxt = i;
        }
    }
}

void solve(int tc) {
    int m; cin >> m;
    map<char, int> idx;

    for (char i = 'a'; i <= 'z'; i++) idx[i] = i - 'a';
    for (char i = 'A'; i <= 'Z'; i++) idx[i] = i - 'A' + 26;

    for (char i = 'a'; i <= 'z'; i++) {
        for (char j = 'A'; j <= 'Z'; j++) adj[idx[i]][idx[j]] = 1e9, adj[idx[j]][idx[i]] = 1e9;
    }

    for (int i = 0, w; i < m; i++) {
        char a,b; cin >> a >> b >> w;;
        int x = idx[a], y = idx[b];
        adj[x][y] = min(adj[x][y], w);
        adj[y][x] = min(adj[y][x], w);
    }

    dijkstra(idx['Z']);
    int ans = 1e18;
    char x;
    for (char i = 'A'; i < 'Z'; i++) {
        cout << dis[idx[i]] << '\n';
        int ix = idx[i];
        if (dis[ix] < ans) {
            ans = dis[x];
            x = i;
        }
    }
    // cout << x << ' ' << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++){
        solve(i);
    }
}