（1）数据13的精度要求比较高，建议使用eps判断能量是否已经消耗完毕，或者直接判断小于0而不是判断<eps。 （2）关于有重边的问题，建议使用链式前向星存边，然后记录下最短路树的父边编号，而不是父节点 （3）关于输入中存在n为起点的边，应该要去掉，或者后续合并可持续化左偏树时忽略n节点也行

const int inf_int = 0x3f3f3f3f;
const ll inf_ll = 0x3f3f3f3f3f3f, inf_2 = 4e13 + 11;
const ll maxn = 1e4 + 3, maxe = 5e5 + 11, mod = 1e6;
const lld eps = 1e-4;

#define PDI pair<double, int>
int n, m;
double dis[maxn], totE, tmpw;

struct Graph {
  int tot, head[maxn];
  struct EDGE {
    int to, nxt;
    double w;
  } e[maxe];
  void init() { tot = 0, me(head, 0); };
  void addEdge(int x, int y, double w) {
    e[++tot] = {y, head[x], w}, head[x] = tot;
  }
} F, E;

struct Tree {
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define nx(x) tr[x].nx
#define val(x) tr[x].w
#define dis(x) tr[x].dis
  int dis, ls, rs, nx;
  double w;
} tr[maxe * 30];
int tot, rt[maxn], pre[maxn], ans;

inline void initTree() {
  dis(0) = -1, tot = ls(0) = rs(0) = nx(0) = val(0) = 0;
}

inline int newNode(int f, double w) {
  ++tot, ls(tot) = rs(tot) = dis(tot) = 0;
  nx(tot) = f, val(tot) = w;
  return tot;
}

inline int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (val(x) > val(y)) swap(x, y);
  int ro = ++tot;
  tr[ro] = tr[x];  // 全都要clone过来
  rs(ro) = merge(rs(ro), y);
  if (dis(ls(ro)) < dis(rs(ro))) swap(ls(ro), rs(ro));
  dis(ro) = dis(rs(ro)) + 1;
  return ro;
}

inline void dijkstra(int s) {
  priority_queue<PDI, vector<PDI>, greater<PDI>> q;
  for (int i = 1; i <= n; i++) dis[i] = 1e18, pre[i] = 0;
  q.push(mp(0, s)), dis[s] = 0;
  while (q.size()) {
    PDI it = q.top();
    q.pop();
    if (it.fi - eps > dis[it.se]) continue;
    for (int v, i = F.head[it.se]; i; i = F.e[i].nxt) {
      double w = F.e[i].w;
      v = F.e[i].to;
      if (dis[v] - eps > w + dis[it.se]) {
        dis[v] = w + dis[it.se], pre[v] = i; // 这里
        q.push(mp(dis[v], v));
      }
    }
  }
}

inline void solve() {
  read(n, m), scanf("%lf", &totE);
  for (int i = 1, x, y; i <= m; i++) {
    read(x, y), scanf("%lf", &tmpw);
    if (x == n) continue; // 这里
    E.addEdge(x, y, tmpw), F.addEdge(y, x, tmpw);
  }
  dijkstra(n);
  vector<int> id(n);
  iota(id.begin(), id.end(), 1);
  sort(id.begin(), id.end(), [&](int i, int j) { return dis[i] < dis[j]; });
  initTree();
  for (int &x : id) {
    for (int i = E.head[x], v; i; i = E.e[i].nxt) {
      double w = E.e[i].w;
      v = E.e[i].to;
      if (i != pre[x]) rt[x] = merge(rt[x], newNode(v, w - dis[x] + dis[v]));
    }
    if (rt[E.e[pre[x]].to]) rt[x] = merge(rt[x], rt[E.e[pre[x]].to]);
  }
  if (totE < dis[1]) {
    puts("0");
    return;
  }
  priority_queue<PDI, vector<PDI>, greater<PDI>> q;
  totE -= dis[1], ans = 1;
  if (rt[1]) q.push(mp(val(rt[1]), rt[1]));
  while (q.size()) {
    PDI it = q.top();
    q.pop();
    totE -= dis[1] + it.fi;
    if (totE < -eps) break; //// 这里
    ans++;
    int x = it.se;
    if (ls(x)) q.push(mp(it.fi - val(x) + val(ls(x)), ls(x)));
    if (rs(x)) q.push(mp(it.fi - val(x) + val(rs(x)), rs(x)));
    if (rt[nx(x)]) q.push(mp(it.fi + val(rt[nx(x)]), rt[nx(x)]));
  }
  printf("%d\n", ans);
}