#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 100 + 10, INF = 0x7ffffff;
int n, m, k, d;
int f[N][N], a, b, c;
int main() {
    freopen("travela.in", "r", stdin);
    freopen("travela.out", "w", stdout);
    while(scanf("%d %d %d", &n, &m, &k), n + m + k) {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                f[i][j] = INF;
        for(int i=0; i<m; i++) {
            scanf("%d %d %d", &a, &b, &c);
            f[a][b] = c;
        }
        for(int k=0; k<n; k++)
            for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        d = f[0][n-1];
        printf("%d\n", d);
    }
    return 0;
}