spfa

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 2147483647
#define N 500000+50
int dis[N];
int vis[N];
int head[N];
int n,m,s;
int num=0;
struct edge
{
    int next,v,to;
}edge[N];
void addedge(int from,int to,int v)
{
    edge[++num].next=head[from];
    head[from]=num;
    edge[num].to=to;
    edge[num].v=v;
}
void spfa()
{
    queue<int>q;
    rep(i,1,n)
    dis[i]=inf,vis[i]=0;

    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].v)
            {
                dis[v]=dis[u]+edge[i].v;
                if(vis[v]==0)
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    rep(i,1,m)
    {
        int a,b,c;
        RIII(a,b,c);
        addedge(a,b,c);//有向边
    }
    spfa();
    return 0;
}

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
#define M 20005
using namespace std;
int n,m,t,oo;
int v[M],w[M],next[M];
int d[N],cnt[N],first[N];
bool flag,vis[N];
void add(int x,int y,int z)
{
        t++;
        next[t]=first[x];
        first[x]=t;
        v[t]=y;
        w[t]=z;
}
bool SPFA(int s)
{
        int x,y,i,j;
        queue<int>q;
        memset(d,127,sizeof(d));
        memset(vis,false,sizeof(vis));
        while(!q.empty())  q.pop();
        d[s]=0;
        cnt[s]=1;
        q.push(s);
        vis[s]=true;
        while(!q.empty())
        {
                x=q.front();
                q.pop();
                vis[x]=false;
                for(i=first[x];i;i=next[i])
                {
                        y=v[i];
                        if(d[y]>d[x]+w[i])
                        {
                                d[y]=d[x]+w[i];
                                cnt[y]=cnt[x]+1;
                                if(cnt[y]>n)
                                  return false;
                                if(!vis[y])
                                {
                                        q.push(y);
                                        vis[y]=true;
                                }
                        }
                }
        }
        return true;
}
int main()
{
        int x,y,z,i;
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);
                add(y,x,z);
        }
        flag=SPFA(1);
        if(!flag)  printf("Yes\n");
        else  printf("No\n");
        return 0;
}