#include <cstdio>
#include <string.h>

#define Nmax 512
#define Pmax 64

int n, m, p;
int cost[Nmax][Nmax];

void citire()
{
    int i, a, b, c;
    
    memset(cost, 0x3f, sizeof(cost));
    
    scanf("%d", &p);
    scanf("%d", &n);
    scanf("%d", &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        cost[a][b] = cost[b][a] = c;
    }
}

void royfloyd()
{
    int i, j, k;
    
    for (i = 1; i <= n; ++i)
        cost[i][i] = 0;
    
    for (k = 1; k <= n; ++k)
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= n; ++j)
                if (cost[i][k] + cost[k][j] < cost[i][j])
                    cost[i][j] = cost[i][k] + cost[k][j];
}

void solve()
{
    int i, j;
    
    royfloyd();
    
}

int main()
{
    freopen("team.in", "r", stdin);
    freopen("team.out", "w", stdout);
    citire();
    solve();
    return 0;
}