Primăria din Iași a hotărât să modernizeze șoselele din localitate. O șosea este o porțiune de drum care unește două intersecții. Firma constructoare a făcut un studiu pentru a determina costurile pentru fiecare șosea. Fondurile sunt limitate, astfel că în prima fază vor fi modernizate doar drumurile din apropierea Palas-ului, care se află la intersecția cu numărul 1. Mai precis: orice șosea modernizată trebuie sa fie cel puțin la fel de aproape de Palas ca orice șosea ce nu va fi modernizată.

Lungimea drumului dintre două intersecții a și b este numărul cel mai mic de intersecții ce trebuie parcurse pentru a ajunge de la a la b. Șoseaua (a, b) este mai aproape de Palas față de șoseaua (c, d) dacă lungimea drumului de la Palas până la cea mai apropiată intersecție dintre a și b este mai mică decât până la cea mai apropiată intersecție dintre c și d. Dacă lungimile drumurilor până la cele mai apropiate intersecții sunt egale, se compară lungimile drumurilor până la celelalte două intersecții. De exemplu dacă pentru șoselele (4, 7) și (3, 5) avem distanțele de la Palas până la intersecțiile: 3, 4, 5, 7 egale cu: 10, 10, 10, 11 în această ordine, atunci (3, 5) e mai aproape de Palas față de (4, 7) deoarece distanțele minime sunt ambele egale cu 10 dar distanța până la intersecția 3 este tot 10, mai mică față de distanța până la intersecția 7 care este 11. Dacă nu există cale de acces de la Palas la o intersecție a atunci șoselele legate de a nu vor fi modernizate.

Cerința

Cunoscând: N – numărul de intersecții din oraș codificate prin numere naturale din mulțimea 1..N, M – numărul de șosele și șoselele împreună cu costul de modernizare, și F – fondurile de care dispune primăria, să se afle K – numărul maxim de șosele care pot fi modernizate.

Date de intrare

În fișierul de intrare modernizare.in se află pe prima linie N, M şi F reprezentând numărul de intersecții, numărul de șosele şi respectiv fondurile totale F. Următoarele M linii conțin triplete de numere naturale a b c, unde (a, b) reprezintă șoseaua ce leagă intersecțiile a și b, iar c este costul de modernizare. Pentru orice linie (a, b) avem: a ≠ b și nu mai există o altă linie cu (a, b) sau (b, a).

Date de ieșire

În fișierul de ieșire modernizare.out se va afla pe prima linie un singur număr natural K, reprezentând numărul maxim de șosele care pot fi modernizate conform restricțiilor.

Restricții și precizări

• 1 ≤ N, M ≤ 100000
• 1 ≤ a, b ≤ N
• 1 ≤ F, c ≤ 2.000.000.000
• N ≤ 1000, pentru teste în valoare de 50 puncte.
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

Exemplu

modernizare.in

4 5 9
1 2 4
2 4 1
3 1 2
3 4 3
3 2 3

modernizare.out

3

Explicație

Șoselele (1,2) și (1,3) sunt cele mai aproape de intersecția 1. Șoseaua (2,3) este mai aproape de Palas față de (2,4) și (3,4) deoarece ambele capete sunt mai aproape de 1. Se modernizează cele trei șosele.

#include <bits/stdc++.h>



using namespace std;

#define inf 1000000000000000001;

ifstream cin("modernizare.in");
ofstream cout("modernizare.out");

long long d[100001];
long long n, mu, f;
vector<vector<pair<long long, long long>>> G(100001);

struct muchie{
    long long i, j, c;
}m[100001];

bool comp(muchie a, muchie b){
    if(min(d[a.i], d[a.j]) != min(d[b.i], d[b.j]))
        return min(d[a.i], d[a.j]) < min(d[b.i], d[b.j]);
    if(max(d[a.i], d[a.j]) != max(d[b.i], d[b.j]))
        return max(d[a.i], d[a.j]) < max(d[b.i], d[b.j]);
    return a.c < b.c;
}

void BFS(){
    d[1] = 0;
    for(int i = 2; i <= n; ++i)
        d[i] = inf;
    queue<int> Q;
    Q.push(1);
    while(!Q.empty()){
        int nod = Q.front();
        for(auto x:G[nod])
            if(d[x.first] > d[nod] + 1)
                d[x.first] = d[nod] + 1, Q.push(x.first);
        Q.pop();
    }
}

int main(){
    cin >> n >> mu >> f;
    for(int i = 1; i <= mu; ++i){
        cin >> m[i].i >> m[i].j >> m[i].c;
        G[m[i].i].push_back(make_pair(m[i].j, m[i].c));
        G[m[i].j].push_back(make_pair(m[i].i, m[i].c));
    }
    BFS();
    sort(m + 1, m + mu + 1, comp);
    int cnt = 0;
    for(int i = 1; i <= mu && f; ++i){
        if(d[m[i].i] != 1000000000000000001){
            f -= m[i].c;
            if(f >= 0)
                cnt++;
        }
    }
    cout << cnt;
}