Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define MAXM 1000010

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

struct edges

{

	int u,v,w;

}es[MAXM];

struct edge

{

	int to,nxt,w;

}e[MAXM];

int edgenum = 0;

int lin[MAXN] = {0};

int ind[MAXN];

void add(int a,int b,int c)

{

	++ind[b];

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

int topo[MAXN];

int d[MAXN],/*最长路*/d_[MAXN]/*最后一条边不为0的最长路*/;

vector<int> v[MAXN];

bool tag[MAXN];

int ans1[MAXN];

int cnt[MAXN];

#define MOD 998244353

#define iter vector<int>::iterator

int cnt2[MAXN];

int dfn[MAXN],low[MAXN],tot = 0;

int stack[MAXN],top = 0;

bool vis[MAXN];

int scc = 0,ins[MAXN],siz[MAXN];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	stack[++top] = k;vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(vis[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(low[k] >= dfn[k])

	{

		int t;++scc;

		do

		{

			t = stack[top--];

			ins[t] = scc;

			vis[t] = false;

			++siz[scc];

		}while(t != k);

	}

	return;

}

edge ve[MAXM];

int vedgenum = 0;

int vlin[MAXN] = {0};

void vadd(int a,int b,int c)

{//cout << a << " " << b << " " << c << endl;

	++ind[b];

	ve[++vedgenum] = (edge){b,vlin[a],c};vlin[a] = vedgenum;

	return;

}

int main()

{

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

	bool flag = false;

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

	{

		es[i].u = rd();es[i].v = rd();es[i].w = rd();

		flag |= (es[i].w != 0);

		add(es[i].v,es[i].u,es[i].w);

	}

	for(int i = 1;i <= n;++i)if(dfn[i] == 0)tarjan(i);

	memset(ind,0,sizeof(ind));

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

		for(int i = lin[k];i != 0;i = e[i].nxt)

			if(ins[k] != ins[e[i].to])vadd(ins[k],ins[e[i].to],e[i].w);

	for(int i = 1;i <= m;++i)if(ins[es[i].u] == ins[es[i].v])++siz[ins[es[i].u]];

	if(!flag)

	{

		queue<int> q;

		for(int i = 1;i <= scc;++i)if(siz[i] != 1)

		{

			puts("0");

			puts("inf");

			return 0;

		}

		for(int i = 1;i <= scc;++i)cnt[i] = siz[i];

		for(int i = 1;i <= scc;++i)if(ind[i] == 0)q.push(i);

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = vlin[k];i != 0;i = ve[i].nxt)

			{

				cnt[ve[i].to] = (cnt[ve[i].to] + cnt[k]) % MOD;

				--ind[ve[i].to];

				if(ind[ve[i].to] == 0)q.push(ve[i].to);

			}

		}

		int ans = 0;

		for(int i = 1;i <= scc;++i)ans = (ans + cnt[i]) % MOD;

		cout << 0 << endl << ans << endl;

		return 0;

	}

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

	{

		if(es[i].w != 0 && ins[es[i].u] == ins[es[i].v])

		{

			puts("inf");

			puts("inf");

			return 0;

		}

		if(ins[es[i].u] == ins[es[i].v])siz[ins[es[i].u]]++;

	}

	queue<int> q;

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

	{

		if(ind[i] == 0)q.push(i);

	}

	topo[0] = scc;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		topo[topo[0]--] = k;

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			--ind[ve[i].to];

			if(ind[ve[i].to] == 0)q.push(ve[i].to);

		}

	}

	int maxlen = 0;

	for(int p = 1;p <= scc;++p)

	{

		int k = topo[p];

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			d[k] = max(d[k],d[ve[i].to] + 1);

			if(ve[i].w != 0)d_[k] = max(d_[k],d[ve[i].to] + 1);

		}

		v[d[k]].push_back(k);

		maxlen = max(maxlen,d_[k]);

	}

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

	{

		if(d_[k] != maxlen)continue;

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			if(d[ve[i].to] + 1 == d_[k])ans1[maxlen] = max(ans1[maxlen],ve[i].w);

		}

	}

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

	{

		if(d_[k] != maxlen)continue;

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			if(d[ve[i].to] + 1 == d_[k] && ve[i].w == ans1[maxlen])tag[ve[i].to] = true;

		}

	}

	for(int p = maxlen - 1;p > 0;--p)

	{

		for(iter it = v[p].begin();it != v[p].end();++it)

		{

			int k = *it;

			if(!tag[k])continue;

			for(int i = vlin[k];i != 0;i = ve[i].nxt)

			{

				if(d[ve[i].to] + 1 == d[k])ans1[p] = max(ans1[p],ve[i].w);

			}

		}

		for(iter it = v[p].begin();it != v[p].end();++it)

		{

			int k = *it;

			if(!tag[k])continue;

			for(int i = vlin[k];i != 0;i = ve[i].nxt)

			{

				if(d[ve[i].to] + 1 == d[k] && ve[i].w == ans1[p])tag[ve[i].to] = true;

			}

		}

	}

	for(iter it = v[0].begin();it != v[0].end();++it)if(tag[*it])cnt[*it] = 1;

	for(int p = 1;p < maxlen;++p)

	{

		for(iter it = v[p].begin();it != v[p].end();++it)

		{

			int k = *it;

			if(!tag[k])continue;

			for(int i = vlin[k];i != 0;i = ve[i].nxt)

			{

				if(d[ve[i].to] + 1 == d[k] && ve[i].w == ans1[p])cnt[k] = (cnt[k] + cnt[ve[i].to]) % MOD;

			}

		}

	}

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

	{

		if(d_[k] != maxlen)continue;

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			if(d[ve[i].to] + 1 == d_[k] && ve[i].w == ans1[maxlen])cnt[k] = (cnt[k] + cnt[ve[i].to]) % MOD;

		}

		cnt2[k] = cnt[k];

	}

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

	{

		if(siz[i] != 1 && cnt[i] != 0 && cnt2[i] == 0)

		{

			cout << "inf" << endl << "inf" << endl;

			return 0;

		}

	}

	for(int p = 1;p <= scc;++p)

	{

		int k = topo[p];

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			cnt2[k] = (cnt2[k] + cnt2[ve[i].to]) % MOD;

		}

	}

	for(int i = maxlen;i >= 1;--i)printf("%d",ans1[i]);cout << endl;

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

	{

		if(siz[i] != 1 && (cnt[i] != 0 || cnt2[i] != 0))

		{

			cout << "inf" << endl;

			return 0;

		}

	}	

	int ans2 = 0;

	for(int i = 1;i <= scc;++i)ans2 = (ans2 + cnt2[i]) % MOD;

	cout << ans2 << endl;

	return 0;

}