#include <bits/stdc++.h>
#define MAXN 50000
#define INF 1000000
using namespace std;
int dist[MAXN], vis[MAXN];
ifstream fin("camionas.in");
ofstream fout("camionas.out");
priority_queue< pair<int, int> > pq;//1-distanta, 2-nodul
vector<pair<int, int>> g[MAXN];//graful
void dijkstra(int node){
    memset(dist, INF, sizeof(dist));
    dist[node]=0;//trebuie sa plec, after all
    pq.push(make_pair(0, node));
    while(!pq.empty()){//cata vreme nu am cerecetat totul
        node=pq.top().second;
        pq.pop();//
        if(vis[node]==0){//daca nodul n-a fost vazut
            vis[node]=1;
            for(int i=0; i<g[node].size(); i++){
                if(dist[node]+g[node][i].second<dist[g[node][i].first]){//daca e mai eficient asa
                    dist[g[node][i].first]=dist[node]+g[node][i].second;//modificarile de rigoare
                    pq.push(make_pair(-dist[g[node][i].first], g[node][i].first));
                }
            }
        }
    }
}
    //e void , asa ca aici inchei
int main(){
    int n, m, maxPotholes; fin>>n>>m>>maxPotholes;
    for(int i=0; i<m; i++){
        int x, y, c; fin>>x>>y>>c;
        if(c<maxPotholes)
           c=1;//schimb costul muchiei, peste masa maxima admisa e 1, sub e 0
        else//alte informatii sunt inutile
           c=0;
        g[x].push_back(make_pair(y, c));//construiesc graful cu costul cat trebuie sa fie
        g[y].push_back(make_pair(x, c));
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<g[i].size(); j++){
             fout<<i<<" "<<g[i][j].first<<" "<<g[i][j].second<<"\n";
        }
    }
    dijkstra(1);//acum e banal, bag un dijkstra pe noul graf si cu asta, basta
    fout<<dist[n];
    return 0;
}