为什么LTE啊还有例9RE？啊啊啊啊啊

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 3e3 + 10;
int h[N],e[N*N],ne[N*N],w[N],dist[N],cnt[N],idx,t,n,m;
bool st[N];

void add(int a,int b,int c){
    e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] = idx++;
}

bool spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(q.size()){
        int k = q.front();
        q.pop();
        st[k] = false;
        
        for(int i = h[k]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[k] + w[i]){
                dist[j] = dist[k] + w[i];
                cnt[j] = cnt[k] + 1;
                if(cnt[j] >= n + 1) return 1;
                
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return 0;
}
int main(){
    cin >> t;
    while(t--){
        cin >> n >> m;
        memset(h,-1, sizeof h);
        memset(st,0, sizeof st);
        memset(cnt,0, sizeof cnt);
        memset(w,0,sizeof w);
        memset(e,0,sizeof e);
        memset(ne,0,sizeof ne);
        idx = 0;
        
        for(int i = 0; i < m; i++){
            int a,b,c;
            cin >> a >> b >> c;
            if(c >= 0) add(b,a,c);
            
            add(a,b,c);
        }
        
        if(spfa()) cout << "YES" << endl;
        else cout << "NO" <<endl;
    }
    return 0;
}