第三个点WA了

#include<bits/stdc++.h>
#define re register
#define il inline
#define ll long long
#define MAXN 1005
#define MAXM 5005
#define rep(i,a,b)  for(re int i = a;i <= b;++ i)
#define Rep(i,a,b)  for(re int i = a;i < b;++ i)
#define drep(i,a,b) for(re int i = a;i >= b;-- i)
#define Drep(i,a,b) for(re int i = a;i > b;-- i)
#define star(i,x)   for(re int i = head[x];i;i = e[i].nxt)
#define fin(a)  freopen(#a".in","r",stdin)
#define fout(a) freopen(#a".out","w",stdout)

using namespace std;

il int read(){
    int w = 0,x = 0;
    char ch = 0;
    while(!isdigit(ch)){
        w |= ch == '-';
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

il void write(int x){
    if(x < 0){
        x = -x;
        putchar('-');
    }
    if(x > 9){
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

il int Min(int a,int b){
    return a < b ? a : b;
}

struct edge{
    int to,nxt,w;
}e[MAXM << 1];
int head[MAXN],tot[MAXN],dis[MAXN],cnt = 0;
bool vis[MAXN];
int N,M,MINANS = 19831205;

il void add(int u,int v,int w){
    e[++ cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

il bool spfa(int s){
    deque<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s] = 0;
    vis[s] = 1;
    tot[s] = 1;
    q.push_back(s);

    while(!q.empty()){
        int u = q.front();
        q.pop_front();
        vis[u] = 0;

        star(i,u){
            int v = e[i].to,w = e[i].w;

            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;

                if(!vis[v]){
                    vis[v] = 1;
                    tot[v] ++;

                    if(tot[v] >= N)
                        return 0;

                    if(!q.empty()){
                        if(dis[v] > dis[q.front()])
                            q.push_back(v);
                        else
                            q.push_front(v);
                    }
                    else
                        q.push_back(v);
                }
            }
        }
    }
    return 1;
}



int main(){
    #ifndef ONLINE_JUDGE
    fin(1260);
    fout(1260);
    #endif

    N = read();
    M = read();

    rep(i,1,M){
        int u = read(),v = read(),w = read();
        add(v,u,w);
    }

    rep(i,1,N)
        add(0,i,0);

    if(!spfa(0)){
        puts("NO SOLUTION");
    }

    else{
        rep(i,1,N)
            MINANS = Min(MINANS,dis[i]);
        
        rep(i,1,N)
            printf("%d\n",dis[i] - MINANS);
    }

    return 0;
}