#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int x,val;
};
const int N=2005;
int dis[N],S[N],ans[N];
vector<Edge> G[N];
int n,m;
void Dijkstra(int start){
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	dis[start]=0;
	pq.push(make_pair(dis[start],start));
	while(!pq.empty()){
		int u=pq.top().second;
		pq.pop();
		if(S[u]) continue;
		S[u]=1; 
		for(auto [v,w]:G[u]){
			if(!S[v]&&dis[v]>dis[u]+w){
				ans[v]=ans[u];
				dis[v]=dis[u]+w;
				pq.push(make_pair(dis[v],v));
			}
			else if(dis[v]==dis[u]+w){
				ans[v]+=ans[u];
				ans[v]%=100003;
			}
		}
	}
	return ;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	int u,v,w;
	while(m--){
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	ans[1]=1;
	Dijkstra(1);
	if(dis[n]>=1e9){
		cout<<"No answer"<<endl;
		return 0;
	}cout<<dis[n]<<' '<<ans[n]<<endl;
	return 0;
}