#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
char in[100], out[100];
int A[50][50], B[100];
vector <int> v;
void f(int a, int b, int n, int s){
    int i;
    if(a==n and b == 1) v.push_back(s);
    if(b>1) return;
    for(i=1;i<=n;i++){
        if(A[a][i]>0 and B[i]==0){
            B[i] = 1;
            f(i,b,n,s+A[a][i]);
            f(i,b+1,n,s+(A[a][i])/2);
            B[i] = 0;
        }
    }
    return;
}
int main(){
    int I, i, j, n, m, k, a, b;
    for(I=1;I<51;I++){
        sprintf(in,".%d.in",I);
        freopen(in,"w",stdout);
        for(i=0;i<50;i++) for(j=0;j<50;j++) A[i][j]=0;
        for(i=0;i<100;i++)B[i] = 0;
        n = rand()%10+1;
        if(I>30) n = 10;
        n = max(n,5);
        m = min(rand()%100+1,(n*(n-3))/2);
        m = max(m,2*n);
        k = rand()%100+1;
        printf("%d %d %d\n",n,m,k);
        for(i=0;i<m;i++){
            a = rand()%n+1;
            b = rand()%n+1;
            while(A[a][b] or a == b){
                a = rand()%n+1;
                b = rand()%n+1;
            }
            A[b][a] = A[a][b] = rand()%10000+1;
            
            printf("%d %d %d\n",a,b,A[a][b]);
        }
        v.clear();
        B[1]=1;
        f(1,0, n, 0);
        sort(v.begin(),v.end());
        sprintf(in,".%d.out",I);
        freopen(in,"w",stdout);
        if(v.size()<k) printf("-1\n");
        else printf("%d\n",v[k-1]);
    }
}