#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
struct data {
ll weight; int start, last, index;
data(ll w, int S, int L, int I) {
weight = w; start = S; last = L; index = I;
}
bool operator<(data other) const
{
return weight > other.weight;
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int N, M, K; //cin >> N >> M >> K;
N = 100;
M = 4950;
K = 4852;
vector<vpl> graph(N);
/*F0R(i, M) {
ll A, B, C; cin >> A >> B >> C; A--; B--;
graph[A].pb(mp(C, B));
graph[B].pb(mp(C, A));
}*/
for(int i=0; i<=N-3; i++) {
for(int j=i+1; j<=N-2; j++) {
graph[i].pb(mp(1, j));
graph[j].pb(mp(1, i));
}
}
for(int i=0; i<=N-2; i++) {
graph[i].pb(mp(1000000000, N-1));
graph[N-1].pb(mp(1000000000, i));
}
F0R(i, N) {
sort(all(graph[i]));
}
priority_queue<data> pq; //-weight, edge index, start, next-to-last.
K *= 2;
set<pl> visited;
F0R(i, N) {
pq.push(data(graph[i][0].f, i, i, 0));
visited.insert(mp(i, i));
}
int pops_count = 0;
while (!pq.empty()) {
data cur = pq.top();
pq.pop();
pops_count++;
int nxt = graph[cur.last][cur.index].s;
if (!visited.count(mp(cur.start, graph[cur.last][cur.index].s))) {
visited.insert(mp(cur.start, graph[cur.last][cur.index].s));
//cout << cur.start << " " << nxt << " " << cur.weight << endl;
K--;
if (K == 0) {
cout << "pops count is " << pops_count << endl;
cout << cur.weight << endl; return 0;
}
pq.push(data(cur.weight + graph[nxt][0].f, cur.start, nxt, 0));
}
if (cur.index + 1 < sz(graph[cur.last])) {
pq.push(data(cur.weight - graph[cur.last][cur.index].f + graph[cur.last][cur.index + 1].f, cur.start, cur.last, cur.index + 1));
}
}
return 0;
}
// read the question correctly (ll vs int)
// template by bqi343
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCAoInNzZTQiKQogCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIGNvbXBsZXg8bGQ+IGNkOwogCnR5cGVkZWYgcGFpcjxpbnQsIGludD4gcGk7CnR5cGVkZWYgcGFpcjxsbCxsbD4gcGw7CnR5cGVkZWYgcGFpcjxsZCxsZD4gcGQ7CiAKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiB2ZWN0b3I8bGQ+IHZkOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmw7CnR5cGVkZWYgdmVjdG9yPHBpPiB2cGk7CnR5cGVkZWYgdmVjdG9yPHBsPiB2cGw7CnR5cGVkZWYgdmVjdG9yPGNkPiB2Y2Q7CiAKIAp0ZW1wbGF0ZSA8Y2xhc3MgVD4gdXNpbmcgVHJlZSA9IHRyZWU8VCwgbnVsbF90eXBlLCBsZXNzPFQ+LCByYl90cmVlX3RhZyx0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+OwogCiNkZWZpbmUgRk9SKGksIGEsIGIpIGZvciAoaW50IGk9YTsgaTwoYik7IGkrKykKI2RlZmluZSBGMFIoaSwgYSkgZm9yIChpbnQgaT0wOyBpPChhKTsgaSsrKQojZGVmaW5lIEZPUmQoaSxhLGIpIGZvciAoaW50IGkgPSAoYiktMTsgaSA+PSBhOyBpLS0pCiNkZWZpbmUgRjBSZChpLGEpIGZvciAoaW50IGkgPSAoYSktMTsgaSA+PSAwOyBpLS0pCiAKI2RlZmluZSBzeih4KSAoaW50KSh4KS5zaXplKCkKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBmIGZpcnN0CiNkZWZpbmUgcyBzZWNvbmQKI2RlZmluZSBsYiBsb3dlcl9ib3VuZAojZGVmaW5lIHViIHVwcGVyX2JvdW5kCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQojZGVmaW5lIHNoYW5kb21fcnVmZmxlIHJhbmRvbV9zaHVmZmxlCiAKY29uc3QgaW50IE1PRCA9IDEwMDAwMDAwMDc7CmNvbnN0IGxsIElORiA9IDFlMTg7CmNvbnN0IGludCBNWCA9IDEwMDAwMTsgLy9jaGVjayB0aGUgbGltaXRzLCBkdW1teQogCnN0cnVjdCBkYXRhIHsKICAgIGxsIHdlaWdodDsgaW50IHN0YXJ0LCBsYXN0LCBpbmRleDsKICAgIGRhdGEobGwgdywgaW50IFMsIGludCBMLCBpbnQgSSkgewogICAgICAgIHdlaWdodCA9IHc7IHN0YXJ0ID0gUzsgbGFzdCA9IEw7IGluZGV4ID0gSTsKICAgIH0KICAgIGJvb2wgb3BlcmF0b3I8KGRhdGEgb3RoZXIpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuIHdlaWdodCA+IG90aGVyLndlaWdodDsKICAgIH0KfTsKIAogCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgY2luLnRpZSgwKTsKIAogICAgaW50IE4sIE0sIEs7IC8vY2luID4+IE4gPj4gTSA+PiBLOwogICAgTiA9IDEwMDsKCU0gPSA0OTUwOwoJSyA9IDQ4NTI7CiAgICB2ZWN0b3I8dnBsPiBncmFwaChOKTsKICAgIC8qRjBSKGksIE0pIHsKICAgICAgICBsbCBBLCBCLCBDOyBjaW4gPj4gQSA+PiBCID4+IEM7IEEtLTsgQi0tOwogICAgICAgIGdyYXBoW0FdLnBiKG1wKEMsIEIpKTsKICAgICAgICBncmFwaFtCXS5wYihtcChDLCBBKSk7CiAgICB9Ki8KICAgIGZvcihpbnQgaT0wOyBpPD1OLTM7IGkrKykgewogICAgICAgIGZvcihpbnQgaj1pKzE7IGo8PU4tMjsgaisrKSB7CiAgICAgICAgICAgIGdyYXBoW2ldLnBiKG1wKDEsIGopKTsKICAgICAgICAgICAgZ3JhcGhbal0ucGIobXAoMSwgaSkpOyAgICAKICAgICAgICB9CiAgICB9CiAgICBmb3IoaW50IGk9MDsgaTw9Ti0yOyBpKyspIHsKICAgICAgICBncmFwaFtpXS5wYihtcCgxMDAwMDAwMDAwLCBOLTEpKTsKICAgICAgICBncmFwaFtOLTFdLnBiKG1wKDEwMDAwMDAwMDAsIGkpKTsKICAgIH0KICAKICAgIEYwUihpLCBOKSB7CiAgICAgICAgc29ydChhbGwoZ3JhcGhbaV0pKTsKICAgIH0KIAogICAgcHJpb3JpdHlfcXVldWU8ZGF0YT4gcHE7IC8vLXdlaWdodCwgZWRnZSBpbmRleCwgc3RhcnQsIG5leHQtdG8tbGFzdC4KICAgIEsgKj0gMjsKICAgIHNldDxwbD4gdmlzaXRlZDsKICAgIEYwUihpLCBOKSB7CiAgICAgICAgcHEucHVzaChkYXRhKGdyYXBoW2ldWzBdLmYsIGksIGksIDApKTsKICAgICAgICB2aXNpdGVkLmluc2VydChtcChpLCBpKSk7CiAgICB9CiAgICBpbnQgcG9wc19jb3VudCA9IDA7CiAgICB3aGlsZSAoIXBxLmVtcHR5KCkpIHsKICAgICAgICBkYXRhIGN1ciA9IHBxLnRvcCgpOwogICAgICAgIHBxLnBvcCgpOwogICAgICAgIHBvcHNfY291bnQrKzsKICAgICAgICBpbnQgbnh0ID0gZ3JhcGhbY3VyLmxhc3RdW2N1ci5pbmRleF0uczsKICAgICAgICBpZiAoIXZpc2l0ZWQuY291bnQobXAoY3VyLnN0YXJ0LCBncmFwaFtjdXIubGFzdF1bY3VyLmluZGV4XS5zKSkpIHsKICAgICAgICAgICAgdmlzaXRlZC5pbnNlcnQobXAoY3VyLnN0YXJ0LCBncmFwaFtjdXIubGFzdF1bY3VyLmluZGV4XS5zKSk7CiAgICAgICAgICAgIC8vY291dCA8PCBjdXIuc3RhcnQgPDwgIiAiIDw8IG54dCA8PCAiICIgPDwgY3VyLndlaWdodCA8PCBlbmRsOwogICAgICAgICAgICBLLS07CiAgICAgICAgICAgIGlmIChLID09IDApIHsKICAgICAgICAgICAgICAgIGNvdXQgPDwgInBvcHMgY291bnQgaXMgIiA8PCBwb3BzX2NvdW50IDw8IGVuZGw7CiAgICAgICAgICAgICAgICBjb3V0IDw8IGN1ci53ZWlnaHQgPDwgZW5kbDsgcmV0dXJuIDA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcHEucHVzaChkYXRhKGN1ci53ZWlnaHQgKyBncmFwaFtueHRdWzBdLmYsIGN1ci5zdGFydCwgbnh0LCAwKSk7CiAgICAgICAgfQogICAgICAgIGlmIChjdXIuaW5kZXggKyAxIDwgc3ooZ3JhcGhbY3VyLmxhc3RdKSkgewogICAgICAgICAgICBwcS5wdXNoKGRhdGEoY3VyLndlaWdodCAtIGdyYXBoW2N1ci5sYXN0XVtjdXIuaW5kZXhdLmYgKyBncmFwaFtjdXIubGFzdF1bY3VyLmluZGV4ICsgMV0uZiwgY3VyLnN0YXJ0LCBjdXIubGFzdCwgY3VyLmluZGV4ICsgMSkpOwogICAgICAgIH0KIAogICAgfQogCiAgICByZXR1cm4gMDsKfQogCi8vIHJlYWQgdGhlIHF1ZXN0aW9uIGNvcnJlY3RseSAobGwgdnMgaW50KQovLyB0ZW1wbGF0ZSBieSBicWkzNDM=