stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
//先从左边先行扫描一遍，再从右边扫描一遍，两边加起来直接用总人数相减

    #include <iostream>

    #include <cstring>

    #include <cstdio>

    #include <string>



    using namespace std;



    const int maxn=1e6+10;



    int n;

    int l[maxn],r[maxn];

    char str[maxn];

    int maxx=0;



    int main()

    {

        scanf("%d",&n);

        scanf("%s",str);



        memset(l,0,sizeof(l));

        memset(r,0,sizeof(r));



        for(int i=0;i<n;i++)

        {

            l[i]=l[i-1];

            if(str[i]=='E') {

                    l[i]++;

            }

        }



        for(int i=n-1;i>=0;i--)

        {

            r[i]=r[i+1];

            if(str[i]=='W') {

                    r[i]++;

            }

        }





         for(int i=0;i<n;i++) {

            r[i]=r[i]+l[i];

            maxx=max(r[i],maxx);

         }



         cout<<n-maxx<<endl;









        return 0;

    }


// Faster C++ solution for the same problem (measured speedup: 9.047541105572503x):
#include<bits/stdc++.h>

using namespace std;

#define LL long long int

#define DL double

#define MLL map<LL,LL>::iterator

#define MSL map<string,L>::iterator

#define MLS map<LL,string>::iterator

#define MSS map<string,string>::iterator

#define MCL map<char,LL>::iterator

#define SL set<LL>::iterator

#define SS set<string>::iterator sl

#define G getline

#define SZ size()

#define IN insert

#define C clear()

#define B begin()

#define F front()

#define T top()

#define E end()

#define EM empty()

#define V vector

#define Q queue

#define DQ deque

#define PQ priority_queue

#define ST stack

#define FI first

#define SE second

#define PI acos(-1)

#define PS push

#define PP pop()

#define PSF push_front

#define PSB push_back

#define PPF pop_front()

#define PPB pop_back()

#define U (LL)0

#define endl "\n"

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

map<LL,pair<LL,LL> >v;

V<LL>w;

int main()

{

    FAST;

    LL n,m,i,j,k,p,q,o,l,s,t,z;

    string a;

    cin>>n>>a;

    p=0;

    q=0;

    l=1;

    for(i=1; a[i]; i++)

    {

        if(a[i]=='W')

        {

            p++;

        }

        else

        {

            q++;

        }

        v[i]= {p,q};

    }

    k=q;

    for(i=1; a[i]; i++)

    {

         if(a[i-1]=='W')

         {

             q++;

         }

         if(a[i]=='E')

         {

             q--;

         }

         k=min(k,q);



    }

    cout<<k<<endl;





    return 0;



}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>



using namespace std;

char s[300010];

int ans1[300010],ans2[300010];

int main()

{

    int N;

    scanf("%d",&N);

    scanf("%s",s);

    memset(ans1,0,sizeof(ans1));

    memset(ans2,0,sizeof(ans2));

    //ans1[0]=1;

    for(int i=0;i<N;i++){

        if(s[i]=='E'){

            ans1[i]++;

        }

        ans1[i+1]=ans1[i];

    }

    //ans2[N-1]=1;

    for(int i=N-1;i>=0;i--){

        if(s[i]=='W'){

            ans2[i]++;

        }

        ans2[i-1]=ans2[i];

    }

    int maxx=0,t;

    for(int j=0;j<N;j++){

        t=ans1[j]+ans2[j];

        maxx=max(t,maxx);

    }

    printf("%d\n",N-maxx);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.314023600088625x):
#include<bits/stdc++.h>

using namespace std;

#define LL long long int

#define DL double

#define MLL map<LL,LL>::iterator

#define MSL map<string,L>::iterator

#define MLS map<LL,string>::iterator

#define MSS map<string,string>::iterator

#define MCL map<char,LL>::iterator

#define SL set<LL>::iterator

#define SS set<string>::iterator sl

#define G getline

#define SZ size()

#define IN insert

#define C clear()

#define B begin()

#define F front()

#define T top()

#define E end()

#define EM empty()

#define V vector

#define Q queue

#define DQ deque

#define PQ priority_queue

#define ST stack

#define FI first

#define SE second

#define PI acos(-1)

#define PS push

#define PP pop()

#define PSF push_front

#define PSB push_back

#define PPF pop_front()

#define PPB pop_back()

#define U (LL)0

#define endl "\n"

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

map<LL,pair<LL,LL> >v;

V<LL>w;

int main()

{

    FAST;

    LL n,m,i,j,k,p,q,o,l,s,t,z;

    string a;

    cin>>n>>a;

    p=0;

    q=0;

    l=1;

    for(i=1; a[i]; i++)

    {

        if(a[i]=='W')

        {

            p++;

        }

        else

        {

            q++;

        }

        v[i]= {p,q};

    }

    k=q;

    for(i=1; a[i]; i++)

    {

         if(a[i-1]=='W')

         {

             q++;

         }

         if(a[i]=='E')

         {

             q--;

         }

         k=min(k,q);



    }

    cout<<k<<endl;





    return 0;



}
// Slower C++ solution:
//先从左边先行扫描一遍，再从右边扫描一遍，两边加起来直接用总人数相减

    #include <iostream>

    #include <cstring>

    #include <cstdio>

    #include <string>



    using namespace std;



    const int maxn=1e6+10;



    int n;

    int l[maxn],r[maxn];

    char str[maxn];

    int maxx=0;



    int main()

    {

        scanf("%d",&n);

        scanf("%s",str);



        memset(l,0,sizeof(l));

        memset(r,0,sizeof(r));



        for(int i=0;i<n;i++)

        {

            l[i]=l[i-1];

            if(str[i]=='E') {

                    l[i]++;

            }

        }



        for(int i=n-1;i>=0;i--)

        {

            r[i]=r[i+1];

            if(str[i]=='W') {

                    r[i]++;

            }

        }





         for(int i=0;i<n;i++) {

            r[i]=r[i]+l[i];

            maxx=max(r[i],maxx);

         }



         cout<<n-maxx<<endl;









        return 0;

    }


// Faster C++ solution for the same problem (measured speedup: 9.205275893611482x):


#include <iostream>

#include <string>

#include <algorithm>

#include <climits>



using namespace std;



int main(){

    int N; string S; cin >> N >> S;

    //int totalW = count(S.begin(), S.end(), 'W');

    int totalE = count(S.begin(), S.end(), 'E');

    int MIN = totalE, wPassed = 0, ePassed = 0;

    for (int i = 0; i < N; i++){

        (S[i] == 'W') ? ++wPassed : ++ePassed;

        MIN = min(MIN, totalE-ePassed+wPassed);

    }   cout << MIN << endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>



using namespace std;

char s[300010];

int ans1[300010],ans2[300010];

int main()

{

    int N;

    scanf("%d",&N);

    scanf("%s",s);

    memset(ans1,0,sizeof(ans1));

    memset(ans2,0,sizeof(ans2));

    //ans1[0]=1;

    for(int i=0;i<N;i++){

        if(s[i]=='E'){

            ans1[i]++;

        }

        ans1[i+1]=ans1[i];

    }

    //ans2[N-1]=1;

    for(int i=N-1;i>=0;i--){

        if(s[i]=='W'){

            ans2[i]++;

        }

        ans2[i-1]=ans2[i];

    }

    int maxx=0,t;

    for(int j=0;j<N;j++){

        t=ans1[j]+ans2[j];

        maxx=max(t,maxx);

    }

    printf("%d\n",N-maxx);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.3718002715639495x):


#include <iostream>

#include <string>

#include <algorithm>

#include <climits>



using namespace std;



int main(){

    int N; string S; cin >> N >> S;

    //int totalW = count(S.begin(), S.end(), 'W');

    int totalE = count(S.begin(), S.end(), 'E');

    int MIN = totalE, wPassed = 0, ePassed = 0;

    for (int i = 0; i < N; i++){

        (S[i] == 'W') ? ++wPassed : ++ePassed;

        MIN = min(MIN, totalE-ePassed+wPassed);

    }   cout << MIN << endl;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

char mat[105][105];

int dp[105][105], flag[105][105], x, y;

int f(int n, int m)

{

	if(n==0 && m==0){

		if(mat[0][0] == '.')return 0;

		else return 1;

	}

	if(n < 0 || m < 0)return 1000000;

	if(flag[n][m])return dp[n][m];

	int a = f(n,m-1);

	int b = f(n-1, m);

	if(n > 0){

		if(mat[n-1][m] == '.' && mat[n][m] == '#')b++;

	}

	if(m>0){

		if(mat[n][m-1] == '.' && mat[n][m] == '#')a++;

	}

	dp[n][m]=min(a,b);

	flag[n][m]=1;

	return dp[n][m];

}

int main()

{

	// if(mat[0][0] == '.'){

	// 	dp[0][0]=0;

	// }

	// else dp[0][0]=1;

	// flag[0][0]=1;

	scanf("%d%d",&x,&y);

	char dm;

	scanf("%c",&dm);

	for(int i = 0; i < x; i++){

		for(int j = 0; j < y; j++){

			scanf("%c",&mat[i][j]);

		}

		scanf("%c",&dm);

	}

	printf("%d\n",f(x-1,y-1));

	// for(int i = 0; i < x; i++){

	// 	for(int j = 0; j < y; j++){

	// 		printf("%d ",dp[i][j]);

	// 	}

	// 	cout << endl;

	// }

}

// Faster C++ solution for the same problem (measured speedup: 5.155819804733493x):
#include<cstdio>

#include<algorithm>

using namespace std;



char c[101][102];

int f[101][102];

int main(){

	int n,m;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%s",c[i]+1);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++){

			if(i==1&&j==1){

				f[i][j]=(c[i][j]=='#');

				continue;

			}

			f[i][j]=2e9;

			if(i!=1)f[i][j]=min(f[i][j],f[i-1][j]+(c[i-1][j]=='.'&&c[i][j]=='#'));

			if(j!=1)f[i][j]=min(f[i][j],f[i][j-1]+(c[i][j-1]=='.'&&c[i][j]=='#'));

		}

	printf("%d\n",f[n][m]);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define endl '\n'



using ll = long long;

using pii = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;



#define ff first

#define ss second



#define x first

#define y second



const int N = 200;



pii dir[2] = {

  {1, 0},

  {0, 1}

};



bool a[N][N];

int dp[N][N];



int dfs(pii u, int n, int m) {

  if (u.x == m-1 and u.y == n-1) return a[u.y][u.x];

  if (~dp[u.y][u.x]) return dp[u.y][u.x];

  dp[u.y][u.x] = INT_MAX;

  for (int i = 0; i < 2; i++) {

    pii v = {u.x + dir[i].x, u.y + dir[i].y};

    if (v.x < m and v.y < n) {

      dp[u.y][u.x] = min(dp[u.y][u.x], dfs(v, n, m) + (a[u.y][u.x] and !a[v.y][v.x]));

    }

  }

  return dp[u.y][u.x];

}



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);



  string s;



  int h, w;

  cin >> h >> w;

  cin.ignore();



  for (int i = 0; i < h; i++) {

    for (int j = 0; j < w; j++) {

      char c; cin >> c;

      a[i][j] = (c == '#');

    }

    cin.ignore();

  }



  memset(dp, -1, sizeof dp);



  int ans = dfs({0, 0}, h, w);



  cout << ans << endl;



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1633987098526755x):
#include <bits/stdc++.h>

using namespace std;



#define endl '\n'



using ll = long long;

using pii = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;



#define ff first

#define ss second



#define x first

#define y second



const int N = 200;



bool a[N][N];

int dp[N][N];



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);



  int h, w;

  scanf("%d %d ", &h, &w);



  for (int i = 0; i < h; i++) {

    for (int j = 0; j < w; j++) {

      a[i][j] = (getchar() == '#');

    }

    getchar();

  }



  dp[h-1][w-1] = a[h-1][w-1];

  for (int i = h-1, j = w-2; j >= 0; j--) {

    dp[i][j] = dp[i][j+1] + (a[i][j] and !a[i][j+1]);

  }

  for (int i = h-2, j = w-1; i >= 0; i--) {

    dp[i][j] = dp[i+1][j] + (a[i][j] and !a[i+1][j]);

  }

  for (int i = h-2; i >= 0; i--) {

    for (int j = w-2; j >= 0; j--) {

      dp[i][j] = min(

        dp[i+1][j] + (a[i][j] and !a[i+1][j]),

        dp[i][j+1] + (a[i][j] and !a[i][j+1])

      );

    }

  }



  printf("%d\n", dp[0][0]);



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

#include <queue>

#define REP(i, n) for (int i = 0; i < (n); i++) 



using namespace std;



using ll = long long;



template<class T>

struct BIT {

  vector<T> dat;



  BIT(int n) : dat(n) {}



  void add(int k, T v) {

    for (int i = k + 1; i < dat.size(); i += i & -i) {

      dat[i] += v;

    }

  }



  T sum(int k) {

    T res = 0;

    for (int i = k; i > 0; i -= i & -i) {

      res += dat[i];

    }

    return res;

  }



  T rsum(int k) {

    return sum(dat.size()-1) - sum(k);

  }



  // sum[0..k) >= v

  int lower_bound(T v) {

    if (v == 0) return 0;

    int k = 0;

    for (int i = dat.size() >> 1; i >= 1; i >>= 1) {

      if (dat[k + i] < v) {

        v -= dat[k + i];

        k += i;

      }

    }

    return k + 1;

  }

};



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);

  int Q;

  cin >> Q;

  vector<int> type(Q);

  vector<ll> A(Q), B(Q);

  vector<ll> C;

  for (int i = 0; i < Q; i++) {

    cin >> type[i];

    if (type[i] == 1) {

      cin >> A[i] >> B[i];

      C.push_back(A[i]);

    }

  }

  sort(C.begin(), C.end());

  C.erase(unique(C.begin(), C.end()), C.end());

  BIT<int> bit0(1 << 18);

  BIT<ll> bit1(1 << 18);

  int n = 0;

  ll sumb = 0;

  for (int i = 0; i < Q; i++) {

    if (type[i] == 1) {

      sumb += B[i];

      int k = lower_bound(C.begin(), C.end(), A[i]) - C.begin();

      bit0.add(k, 1);

      bit1.add(k, A[i]);

      n++;

    } else {

      int k = bit0.lower_bound((n + 1) / 2);

      ll x = C[k - 1];

      ll ans = sumb + (x * bit0.sum(k) - bit1.sum(k)) + (bit1.rsum(k) - x * bit0.rsum(k));

      cout << x << ' ' << ans << '\n';

    }

  }

}


// Faster C++ solution for the same problem (measured speedup: 4.10375319739132x):
#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

#include <queue>

#define REP(i, n) for (int i = 0; i < (n); i++) 



using namespace std;



using ll = long long;

template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;

template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>;



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);

  int Q;

  cin >> Q;

  maxheap<ll> L;

  minheap<ll> R;

  ll ans = 0;

  while (Q--) {

    int type;

    cin >> type;

    if (type == 1) {

      ll a, b;

      cin >> a >> b;

      ans += b;

      L.push(a);

      R.push(a);

      if (L.top() > R.top()) {

        ll l = L.top(); L.pop();

        ll r = R.top(); R.pop();

        ans += l - r;

        L.push(r);

        R.push(l);

      }

    } else {

      cout << L.top() << ' ' << ans << '\n';

    }

  }

}
// Slower C++ solution:
#include <iostream>

using namespace std;

long long n, m, a, b, c, d[1005][1005];

int main() {

	int i, j, k;

	cin>>n>>m;

	for(i=1; i<=n; i++) {

		for(j=1; j<=n; j++) d[i][j] = -1e18;

		d[i][i] = 0;

	}

	while(m--) {

		cin>>a>>b>>c;

		d[a][b] = c;

	}

	for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++)

		if(d[i][k] + d[k][j] > d[i][j]) d[i][j] = d[i][k] + d[k][j];

	d[1][1]>0 ? cout<<"inf" : cout<<d[1][n];

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.214753298568395x):
#include <cstdio>

#define N 2010

#define INF 1e18

long long n, m, a[N], b[N], c[N], d[N/2];

int main() {

	int i, j;

	scanf("%lld%lld", &n, &m);

	for(i=0; i<m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

	for(i=1; i<=n; i++) d[i] = -INF;

	d[1] = 0;

	for(i=0; i<n; i++) for(j=0; j<m; j++) {

		if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n-1 && b[j]==n) d[0] = 1;

		}

	}

	d[0] ? puts("inf") : printf("%lld", d[n]);

	return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

long long n, m, a, b, c, d[1005][1005];

int main() {

	int i, j, k;

	cin>>n>>m;

	for(i=1; i<=n; i++) {

		for(j=1; j<=n; j++) d[i][j] = -1e18;

		d[i][i] = 0;

	}

	while(m--) cin>>a>>b>>c, d[a][b] = c;

	for(k=1; k<=n; k++) for(i=1; i<=n; i++) {

		if(d[i][k] == -1e18) continue;

		for(j=1; j<=n; j++) if(d[i][k] + d[k][j] > d[i][j]) d[i][j] = d[i][k] + d[k][j];

	}

	d[1][1]>0 ? cout<<"inf" : cout<<d[1][n];

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2153944332466615x):
#include <cstdio>

#define N 2010

#define INF 1e18

long long n, m, a[N], b[N], c[N], d[N/2];

int main() {

	int i, j;

	scanf("%lld%lld", &n, &m);

	for(i=0; i<m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

	for(i=1; i<=n; i++) d[i] = -INF;

	d[1] = 0;

	for(i=0; i<n; i++) for(j=0; j<m; j++) {

		if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n-1 && b[j]==n) d[0] = 1;

		}

	}

	d[0] ? puts("inf") : printf("%lld", d[n]);

	return 0;

}
// Slower C++ solution:
#include <iostream>

#define N 2005

#define INF 1e18

using namespace std;

typedef long long ll;

ll n, m, a[N], b[N], c[N], d[N];

bool f() {

	int i, j;

	for(i=0; i<=n; i++) d[i]=-INF;

	d[1]=0;

	for(i=0; i<=n; i++) for(j=0; j<m; j++) {

		if(d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n && b[j]==n) return 0;

		}

	}

	return 1;

}



int main() {

	cin>>n>>m;

	for(int i=0; i<m; i++) cin>>a[i]>>b[i]>>c[i];

	f() ? cout<<d[n] : cout<<"inf";

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2085321673591025x):
#include <cstdio>

#define N 2010

#define INF 1e18

long long n, m, a[N], b[N], c[N], d[N/2];

int main() {

	int i, j;

	scanf("%lld%lld", &n, &m);

	for(i=0; i<m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

	for(i=1; i<=n; i++) d[i] = -INF;

	d[1] = 0;

	for(i=0; i<n; i++) for(j=0; j<m; j++) {

		if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n-1 && b[j]==n) d[0] = 1;

		}

	}

	d[0] ? puts("inf") : printf("%lld", d[n]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf=1ll<<50;

typedef pair<ll,ll> ii;

const int N=4e3+20;

ll d[N],n,m;

vector<ii> e[N];

bool neg[N];

void calc()

{

    fill(d,d+1+n,inf);

    memset(neg,false,sizeof(neg));

    d[1]=0;

    for(int k=1;k<n;k++)

    {

        for(int i=1;i<=n;i++)

        {

            for(int j=0;j<e[i].size();j++)

            {

                ll v=e[i][j].first,w=e[i][j].second;

                if(d[i]==inf)

                    continue;

                if(d[v]>d[i]+w)

                    d[v]=d[i]+w;

            }

        }

    }





    for(int k=1;k<=n;k++)

    {

        for(int i=1;i<=n;i++)

        {

            for(int j=0;j<e[i].size();j++)

            {

                ll v=e[i][j].first,w=e[i][j].second;

                if(d[i]==inf)

                    continue;

                if(d[v]>d[i]+w)

                {

                    d[v]=d[i]+w;

                    neg[v]=true;

                }

                if(neg[i]==true)

                    neg[v]=true;

            }

        }

    }

    if(neg[n]==false)

        cout<<-d[n]<<endl;

    else

        puts("inf");



}

int main()

{

    while(cin>>n>>m)

    {

        for(int i=0;i<=n;i++)

            e[i].clear();

        ll u,v,w;

        while(m--)

        {

            cin>>u>>v>>w;

            e[u].push_back(ii(v,-w));

        }

        calc();

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1022210575511364x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1LL << 50;



const int N = 1000 + 10;



int a[N*2], b[N*2];

ll c[N*2];

int main(void)

{

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= m; ++i)

    {

        cin >> a[i] >> b[i] >> c[i];

        c[i] = -c[i];

    }



    ll dist[N];

    bool negative[N];

    memset(dist, 0x3f, sizeof dist);

    memset(negative, 0, sizeof negative);

    dist[1] = 0;



    for (int loop = 0; loop < n - 1; ++ loop)

    {

        for (int i = 1; i <= m; ++i)

        {

            if (dist[b[i]] > dist[a[i]] + c[i])

            {

                dist[b[i]] = dist[a[i]] + c[i];

            }

        }

    }



    ll ans = dist[n];

    for (int loop = 0; loop < n ; ++ loop)

    {

        for (int i = 1; i <= m; ++i)

        {



            if (dist[b[i]] > dist[a[i]] + c[i])

            {

                dist[b[i]] = dist[a[i]] + c[i];

                negative[b[i]] = true;

            }



            if (negative[a[i]] == true)

            {

                negative[b[i]] = true;

            }

        }

    }

    if (negative[n])

        cout << "inf" << endl;

    else

        cout << -ans << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);++i)

#define ALL(A) A.begin(), A.end()

#define INF (1e15)



using namespace std;



typedef long long ll;

typedef pair<int, int> P;



const int MAX_N = 1000;

const int MAX_M = 2000;



int a[MAX_M], b[MAX_M];

ll c[MAX_M];

ll dist[MAX_N];



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	int N, M; cin >> N >> M;



	rep (i, M){

		cin >> a[i] >> b[i] >> c[i];

		--a[i], --b[i];

	} // end rep



	rep (i, N){

		dist[i] = -INF;

	} // end rep



	dist[0] = 0LL;

	rep (update, 5 * MAX_N){

		rep (i, M){

			if (dist[b[i]] < dist[a[i]] + c[i]){

				dist[b[i]] = dist[a[i]] + c[i];

			} // end if

		} // end rep

	} // end rep



	ll ans = dist[N - 1];



	rep (update, 5 * MAX_N){

		rep (i, M){

			if (dist[b[i]] < dist[a[i]] + c[i]){

				dist[b[i]] = dist[a[i]] + c[i];

			} // end if

		} // end rep

	} // end rep



	if (ans != dist[N - 1]){

		cout << "inf" << endl;

	}else{

		cout << ans << endl;

	} // end if



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1264569516045597x):
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);++i)

#define ALL(A) A.begin(), A.end()

#define INF ((ll)(1e15))



using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef pair<int, ll> IL;



const int MAX_N = 1000;

vector<IL> G[MAX_N]; // P(to,cost)



ll dist[MAX_N];



int main()

{

	rep (i, MAX_N) G[i].clear();

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	

	int N, M; cin >> N >> M;

	rep (i, M){

		int a, b; ll c; cin >> a >> b >> c;

		--a, --b;

		G[a].push_back(IL(b,-c));

	} // end rep



	rep (i, N){

		dist[i] = INF;

	} // end rep



	bool negative = false;

	dist[0] = 0LL;

	rep (iter, 2 * N){

		rep (v, N){

 			if (dist[v] == INF) continue;

			for (int j = 0; j < (int)G[v].size(); ++j){

				int u = G[v][j].first;

				ll c = G[v][j].second;

				if (dist[u] > dist[v] + c){

					dist[u] = dist[v] + c;

					if (u == N - 1 && iter >= N){

						negative |= true;

					} // end if

				} // end if

			} // end for

		} // end rep

	} // end rep



	if (!negative){

		cout << -dist[N - 1] << endl;

	}else{

		cout << "inf" << endl;

	} // end if



	return 0;

}