#include<iostream>
#include<algorithm>
#include<vector>
#define max 110
#define size 10000
std::vector<int> v;
int n,e,s,t,k;
int adj[max][max];
using namespace std;
struct st
{
int v;
int dist;
};
struct queue
{
int front;
int rear;
st arr[size];
void insert(st);
st del();
queue();
}q;
queue::queue()
{
front=-1;
rear=-1;
}
st queue::del()
{
if(front!=-1)
{
st f=arr[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=(front+1)%size;
}
return f;
}
}
void queue::insert(st f)
{
rear=(rear+1)%size;
arr[rear]=f;
if(front==-1)
front=0;
}
void reset_adj()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
adj[i][j]=-1;
}
}
}
void make_queue_empty()
{
while(q.front!=-1)
{
st temp=q.del();
}
}
void get_k_longest()
{
int cnt=0;
while(q.front!=-1)
{
st temp=q.del();
for(int i=1;i<=n;i++)
{
if(adj[temp.v][i]>=0)
{
st s1;
s1.v=i;
s1.dist=temp.dist+adj[temp.v][i];
q.insert(s1);
if(i==t)
{
v.push_back(s1.dist);
cnt++;
if(cnt>=size)
return;
}
}
}
}
}
int main()
{
int v1,v2,wt;
while(1)
{
cin>>n>>e;
if((n==0)&&(e==0))
break;
reset_adj();
cin>>s>>t>>k;
for(int i=1;i<=e;i++)
{
cin>>v1>>v2>>wt;
adj[v1][v2]=wt;
}
st s1;
s1.v=s;
s1.dist=0;
q.insert(s1);
get_k_longest();
sort(v.begin(),v.end());
vector <int>::iterator it;
int cnt=0;
for(it=v.begin();it<v.end();it++)
{
cnt++;
if(cnt==k)
{
cout<<*it<<"\n";
make_queue_empty();
v.clear();
break;
}
}
if(cnt<k)
{
make_queue_empty();
v.clear();
cout<<"-1"<<"\n";
}
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8dmVjdG9yPgojZGVmaW5lIG1heCAxMTAKI2RlZmluZSBzaXplIDEwMDAwCnN0ZDo6dmVjdG9yPGludD4gdjsKaW50IG4sZSxzLHQsazsKaW50IGFkalttYXhdW21heF07CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBzdAp7CglpbnQgdjsKCWludCBkaXN0Owp9OwpzdHJ1Y3QgcXVldWUKewoJaW50IGZyb250OwoJaW50IHJlYXI7CglzdCBhcnJbc2l6ZV07Cgl2b2lkIGluc2VydChzdCk7CglzdCBkZWwoKTsKCXF1ZXVlKCk7Cn1xOwpxdWV1ZTo6cXVldWUoKQp7CiAgICAgICBmcm9udD0tMTsKCSAgIHJlYXI9LTE7IAkKfQpzdCBxdWV1ZTo6ZGVsKCkKewoJCglpZihmcm9udCE9LTEpCgl7CgkJc3QgZj1hcnJbZnJvbnRdOwoJCWlmKGZyb250PT1yZWFyKQoJCXsKCQkJZnJvbnQ9LTE7CgkJCXJlYXI9LTE7CgkJfQoJCWVsc2UKCQl7CgkJICBmcm9udD0oZnJvbnQrMSklc2l6ZTsKCSAgICB9CgkJcmV0dXJuIGY7CiAgIH0KICAgICAKfQp2b2lkIHF1ZXVlOjppbnNlcnQoc3QgZikKewoJICAgcmVhcj0ocmVhcisxKSVzaXplOwoJICAgYXJyW3JlYXJdPWY7CgkgICBpZihmcm9udD09LTEpCgkgICAgIGZyb250PTA7CSAgIAp9CnZvaWQgcmVzZXRfYWRqKCkKewoJZm9yKGludCBpPTE7aTw9bjtpKyspCgl7CgkJZm9yKGludCBqPTE7ajw9bjtqKyspCgkJewoJCQlhZGpbaV1bal09LTE7CgkJfQoJfQp9CnZvaWQgbWFrZV9xdWV1ZV9lbXB0eSgpCnsKCXdoaWxlKHEuZnJvbnQhPS0xKQoJewoJCXN0IHRlbXA9cS5kZWwoKTsKCX0KfQp2b2lkIGdldF9rX2xvbmdlc3QoKQp7CglpbnQgY250PTA7Cgl3aGlsZShxLmZyb250IT0tMSkKCXsKCQlzdCB0ZW1wPXEuZGVsKCk7CgkJZm9yKGludCBpPTE7aTw9bjtpKyspCgkJewoJCSAgIGlmKGFkalt0ZW1wLnZdW2ldPj0wKQoJCSAgIHsKCQkgICAJc3QgczE7CgkJICAgCXMxLnY9aTsKCQkgICAJczEuZGlzdD10ZW1wLmRpc3QrYWRqW3RlbXAudl1baV07CgkJICAgCXEuaW5zZXJ0KHMxKTsKCQkgICAJaWYoaT09dCkKCQkgICAJewoJCSAgIAkJdi5wdXNoX2JhY2soczEuZGlzdCk7CgkJICAgCQljbnQrKzsKCQkgICAJCWlmKGNudD49c2l6ZSkKCQkgICAJCSAgIHJldHVybjsKCQkgICAJfQoJCSAgIH0JCgkJfQoJfQp9CmludCBtYWluKCkKeyAKICAgIGludCB2MSx2Mix3dDsKICAgIHdoaWxlKDEpCiAgICB7CiAgICAJY2luPj5uPj5lOwogICAgCWlmKChuPT0wKSYmKGU9PTApKQogICAgCSAgIGJyZWFrOwogICAgCXJlc2V0X2FkaigpOwogICAgCWNpbj4+cz4+dD4+azsKICAgIAlmb3IoaW50IGk9MTtpPD1lO2krKykKICAgIAl7CiAgICAJICAgY2luPj52MT4+djI+Pnd0OwoJCSAgIGFkalt2MV1bdjJdPXd0OwkKICAgIAl9CiAKICAgIAlzdCBzMTsKICAgIAlzMS52PXM7CiAgICAJczEuZGlzdD0wOwogICAgCXEuaW5zZXJ0KHMxKTsKICAgIAlnZXRfa19sb25nZXN0KCk7CiAgICAJc29ydCh2LmJlZ2luKCksdi5lbmQoKSk7CiAgICAJdmVjdG9yIDxpbnQ+OjppdGVyYXRvciBpdDsKICAgIAlpbnQgY250PTA7CgkJZm9yKGl0PXYuYmVnaW4oKTtpdDx2LmVuZCgpO2l0KyspCgkJewoJCSAgIAljbnQrKzsKCQkgICAJaWYoY250PT1rKQoJCSAgIAl7CgkJICAgCQljb3V0PDwqaXQ8PCJcbiI7CgkJICAgCQltYWtlX3F1ZXVlX2VtcHR5KCk7CgkJICAgCQl2LmNsZWFyKCk7CgkJICAgCQlicmVhazsKCQkgICAJfQoJCX0gCgkJaWYoY250PGspCgkJewoJCSAgICAgICAgbWFrZV9xdWV1ZV9lbXB0eSgpOwoJCSAgIAkJdi5jbGVhcigpOwoJCSAgIAkJY291dDw8Ii0xIjw8IlxuIjsKCQl9CgkJICAKICAgIH0KICAgcmV0dXJuIDA7Cn0K
NSA2CjEgNSAyCjEgMiAxCjIgNSAxMAoxIDMgMQozIDUgMTAKMSA0IDEKNCA1IDEwCgo1IDYKMSA1IDMKMSAyIDEKMiA1IDEwCjEgMyAxCjMgNSAxMAoxIDQgMQo0IDUgMTAKCjUgNgoxIDUgNAoxIDIgMQoyIDUgMTAKMSAzIDEKMyA1IDEwCjEgNCAxCjQgNSAxMAoKNSA2CjEgNSA1CjEgMiAxCjIgNSAxMAoxIDMgMQozIDUgMTAKMSA0IDEKNCA1IDEwCjMgMwoKMSAzIDQKCjEgMyAzCgoxIDIgNAoKMiAzIDUKCjUgNgoKNSAyIDUKCjEgMiAyCgoyIDUgNAoKMyAyIDMKCjQgMyAxCgo1IDEgMwoKNSA0IDIKCjIgMgoKMSAyIDMKCjEgMiA1CgoyIDIgMgoKCjUgNgoKNSAyIDIKCjEgMiAyCgoyIDUgNAoKMyAyIDMKCjQgMyAxCgo1IDEgMwoKNSA0IDIKNSA2Cgo1IDIgMwoKMSAyIDIKCjIgNSA0CgozIDIgMwoKNCAzIDEKCjUgMSAzCgo1IDQgMgo1IDYKCjUgMiA0CgoxIDIgMgoKMiA1IDQKCjMgMiAzCgo0IDMgMQoKNSAxIDMKCjUgNCAyCjUgNgoKNSAyIDUKCjEgMiAyCgoyIDUgNAoKMyAyIDMKCjQgMyAxCgo1IDEgMwoKNSA0IDIKNSA2Cgo1IDIgNgoKMSAyIDIKCjIgNSA0CgozIDIgMwoKNCAzIDEKCjUgMSAzCgo1IDQgMgo1IDYKCjUgMiA3CgoxIDIgMgoKMiA1IDQKCjMgMiAzCgo0IDMgMQoKNSAxIDMKCjUgNCAyCjUgNgoKNSAyIDgKCjEgMiAyCgoyIDUgNAoKMyAyIDMKCjQgMyAxCgo1IDEgMwoKNSA0IDIKNSA2Cgo1IDIgOQoKMSAyIDIKCjIgNSA0CgozIDIgMwoKNCAzIDEKCjUgMSAzCgo1IDQgMgo1IDYKCjUgMiAxMAoKMSAyIDIKCjIgNSA0CgozIDIgMwoKNCAzIDEKCjUgMSAzCgo1IDQgMgoKMCAwCg==
5 6
1 5 2
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
5 6
1 5 3
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
5 6
1 5 4
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
5 6
1 5 5
1 2 1
2 5 10
1 3 1
3 5 10
1 4 1
4 5 10
3 3
1 3 4
1 3 3
1 2 4
2 3 5
5 6
5 2 5
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
2 2
1 2 3
1 2 5
2 2 2
5 6
5 2 2
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 3
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 4
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 5
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 6
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 7
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 8
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 9
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
5 6
5 2 10
1 2 2
2 5 4
3 2 3
4 3 1
5 1 3
5 4 2
0 0