/*题目描述：原点到所有点的最短路径，使用djkstra算法 */
/* http://acm.tju.edu.cn/toj/showp2870.html 题目测试连接 */
/* by jiajie999*/
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define Max_Num_City 210
#define MAXINT 21474836 //注意这个值不能太大
int dist[Max_Num_City];
char visited[Max_Num_City];
int c[Max_Num_City][Max_Num_City];
int n, m, k;
void djkstra()
{
int i, j;
for (i = 1; i <= n; i++)
{
dist[i] = c[0][i];
visited[i] = false;
}
dist[0] = MAXINT;
while (1)
{
j = 0;
for (i = 1; i <= n; i++)
if (!visited[i] && dist[i] < dist[j])
j = i;
if (j == 0)
break;
visited[j] = true;
for (i = 1; i <=n; i++)
if (!visited[i] && dist[j] + c[j][i] < dist[i])
dist[i] = dist[j] + c[j][i];
}
}
int main()
{
while (cin >> n)
{
if (n == 0)
break;
cin >> m;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
{
c[i][j] = MAXINT;
}
/*read info. */
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
cin >> c[x][y];
}
cin >> k;
djkstra();
map < int, int > my;
my.clear();
for (int i = 0; i <= n; i++)
my[i] = dist[i];
sort(dist, dist + n+1);
for (int i = 0; i <= n; i++)
if (my[i] == dist[k - 1])
{
cout << i << endl;
break;
}
}
return 0;
}
/*
2870. The K-th City
--------------------------------------------------------------------------------
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 565 Accepted Runs: 205
--------------------------------------------------------------------------------
Given a map of your country, there are N cities. The cities are labeled as 0, 1, ..., N - 1, and you live in city 0. Can you calculate out the K-th nearest city form you? If two or more cities have the same distance form you, you may assume that the city with smaller label is nearer than the city with bigger one.
Input
There are several cases. The first line of each case is two integers N and M (1 ≤ N ≤ 200, 0 ≤ M ≤ 10000), which is the number of cities in your country and the total number of roads in your country. There are three integers in each of the following M lines, A, B, C, which descript one road. A and B are the two cities that connected by that road, and C is the length of that road (1 ≤ C ≤ 2000). The roads are of both directions, and no two roads connect two same cities. There is at least one path between any two cities. At the last line of each case is a single integer K (1 ≤ K < N).
The last case is followed by a line with a single 0.
Output
Print the label of the K-th nearest city.
Sample Input
4 3
0 1 120
0 2 180
1 3 40
3
4 3
0 1 120
0 3 60
3 2 30
1
0
Sample Output
2
3
*/
/*
Here is my accepted code using warshall. Hope it helps( btw, I thought warshall would time out in the contest, so in fact I used dijkstra in there)
//
ID: trulo_11
PROG:
LANG: C++
//
#include<stdio.h>
#define F(i,a,n)for(int i=a;i<n;++i)
#define pii pair<int,int>
#include<algorithm>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<fstream>
#include<string>
#include<sstream>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<queue>
#define oo 1000000000
#define all(v) (v).begin(),(v).end()
#define Fe(it,v)for(__typeof__((v).begin()) it=(v).begin();it!=(v).end();++it)
using namespace std;
int main(){
int n,m;
int f[200][200];
while(scanf("%d",&n)==1&&n){
F(i,0,n)F(j,0,n)f[i][j]=oo;
F(i,0,n)f[i][i]=0;
scanf("%d",&m);
F(i,0,m){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
f[a][b]=f[b][a]=c;
}
F(k,0,n)F(i,0,n)F(j,0,n){
int t=f[i][k]+f[k][j];
if(t<f[i][j])f[i][j]=t;
}
pii a[200];
F(i,0,n)a[i]=pii(f[0][i],i);
sort(a,a+n);
int k;
scanf("%d",&k);
printf("%d/n",a[k].second);
}
}
*/