#include<bits/stdc++.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <numeric>
#include <bitset>
#define endl '\n'
#define ll long long
#define all(n) n.begin() , n.end( )
#define vi vector<int>
#define vvi vector<vi>
#define int long long
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define mii map<int,int>
#define si set<int>
#define input(v,n) for(int i = 0 ; i< n ; i++) cin >> v[i]
#define output(v) for(auto it : v) cout << it << endl;
#define IS_POWER_OF_TWO(n) ((n) && !((n) & ((n) - 1)))
#define bug(...) _f (#__VA_ARGS__,__VA_ARGS__)
#define lb(x,w,z) for(int x=w;x<z;x++)
#define FOR (x,y) for(auto x:y)
#define revlop(a,b,c) for(int a=b;a>=c;a--)
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace std;
// using namespace __gnu_pbds;
// template<class t> using ordered_multiset = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
//---------------------------------------------------------------
int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
using namespace std;
void fast() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
// const ll N= 2e6+5;
// ll pre[N],pre2[N],next_arr[N],arr[N],bb[N] ;
/*
ll sqrtt(ll n){
ll l{},r= 1000000000+1,mid;
while(r-l>1){
mid = l+(r-l)/2;
if( mid * mid > n )r=mid;
else l =mid;
}
return l;
}
ll lcm ( ll a , ll b)
{
return (a*b)/gcd(a,b);
}
ll fast_power(ll a,ll b , int mod){
ll ans=1;
while(b){
if(b&1){
ans*=a;
ans%=mod;
}
a*=a;
a%=mod;
b = (b>>1);
}
return ans;
}
/*
ll gcd ( ll a, ll b)
{
if ( b == 0 )
return a;
return gcd(b, a%b);
}
vector<int> vis(N);
vector<int> prime(N ) ;
void get_prime(){
prime[0] = 0 , prime[1] = 1 ;
for (int i = 2 ; i<= N ; i++){
if ( !prime[i] ){
for (int j = i ; j <= N ; j+=i)
prime[j] = i ;
}
}
}
vi prims(N);
void seive(int n ){
prims[0] = prims[1] = 1;
for (int i = 2 ; i* i <= n ; i++){
if ( !prims[i] ){
prims[i] = 0 ;
for (int j = 2*i ; j <= n ; j+=i ){
prims[j] = 1;
}
}
}
}
vector<int> prim_fac(ll n ){
vector<int> v;
for (int i = 2 ; i*i <= n ;i ++ ){
while (n != 1 ){
if ( n % i == 0 ){
n/=i;
v.push_back(i);
}
else break;
}
}
return v;
}
bool is_prime(int n)
{
bool isprime = true;
if ( n == 1)
return false;
for (int i = 2 ; i * i <= n ; i++)
{
if ( n %i == 0 )
isprime = false;
}
return isprime;
}*/
const ll oo = 1e18+2 , mod = 1e9+7 ;
const int N = 1e5+5;
vector<pair<int,int>> adj[N] ;
vector<int> dist(N, oo) , ans , path(N) , mn (N) , mx(N) ;
map<int,int> mp;
map<int, vector<int>> flights;
int n , m , k ;
void dijkstra( int src ) {
priority_queue< pii , vector<pii> , greater<>> pq;
pq.push({ 0, src});
dist[src] = 0 ;
mn[1] = 0 , mx [1 ] = 0 , path[1] = 1 ;
while ( !pq.empty()){
int curr = pq.top().second;
int d = pq.top().first;
pq.pop();
if ( dist[curr] != d){
continue;
}
for (auto it : adj[curr]){
if ( dist[it.first] > it.second + d ){
dist[it.first] = it.second + d ;
pq.push({dist[it.first] , it.first});
path[it.first] = path[curr];
mn[it.first] = mn[curr]+1;
mx[it.first] = mx[curr] + 1 ;
}
else if ( dist[it.first] == it.second + d ){
path[it.first] = ( path[it.first] % mod + path[curr]%mod ) % mod ;
mn[it.first] = min ( mn[it.first] , mn[curr] +1 );
mx[it.first] = max ( mx[it.first] , mx[curr] +1 );
}
}
}
}
void solve( ){
cin >> n >> m ;
while ( m -- ){
int a , b , w ;
cin >> a >> b >> w ;
adj[a].push_back({b,w });
}
dijkstra(1);
cout << dist[n] << ' ' << path[n] << ' ' << mn[n] <<' '<< mx[n] << endl;
}
signed main( )
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
//#endif
fast();
int t =1;
clock_t w =clock();
// cin >> t ;
while ( t -- ){
solve();
}
// cerr << "Run time : " << ((double) (clock() - w) / CLOCKS_PER_SEC);
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxudW1lcmljPgojaW5jbHVkZSA8Yml0c2V0PgojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGFsbChuKSBuLmJlZ2luKCkgLCBuLmVuZCggKQojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdnZpIHZlY3Rvcjx2aT4KI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSB2cGlpIHZlY3RvcjxwYWlyPGludCxpbnQ+PgojZGVmaW5lIG1paSBtYXA8aW50LGludD4KI2RlZmluZSBzaSBzZXQ8aW50PgojZGVmaW5lIGlucHV0KHYsbikgZm9yKGludCBpID0gMCA7IGk8IG4gOyBpKyspIGNpbiA+PiB2W2ldCiNkZWZpbmUgb3V0cHV0KHYpICBmb3IoYXV0byBpdCA6IHYpIGNvdXQgPDwgaXQgPDwgZW5kbDsKI2RlZmluZSBJU19QT1dFUl9PRl9UV08obikgKChuKSAmJiAhKChuKSAmICgobikgLSAxKSkpCiNkZWZpbmUgYnVnKC4uLikgX2YgKCNfX1ZBX0FSR1NfXyxfX1ZBX0FSR1NfXykKIAojZGVmaW5lIGxiKHgsdyx6KSBmb3IoaW50IHg9dzt4PHo7eCsrKQojZGVmaW5lIEZPUiAoeCx5KSBmb3IoYXV0byB4OnkpCiNkZWZpbmUgcmV2bG9wKGEsYixjKSBmb3IoaW50IGE9YjthPj1jO2EtLSkKIAovLyAjaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+Ci8vICNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgovLyB1c2luZyBuYW1lc3BhY2Ugc3RkOwovLyB1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKLy8gdGVtcGxhdGU8Y2xhc3MgdD4gdXNpbmcgb3JkZXJlZF9tdWx0aXNldCA9IHRyZWU8dCwgbnVsbF90eXBlLCBsZXNzPHQ+LCByYl90cmVlX3RhZywgdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPjsKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIAppbnQgZHhbXSA9IHswLCAwLCAtMSwgMSwgLTEsIC0xLCAxLCAxfTsKaW50IGR5W10gPSB7MSwgLTEsIDAsIDAsIDEsIC0xLCAxLCAtMX07CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdm9pZCBmYXN0KCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogICAgY291dC50aWUoTlVMTCk7Cn0KIAovLyBjb25zdCBsbCAgTj0gMmU2KzU7Ci8vIGxsICBwcmVbTl0scHJlMltOXSxuZXh0X2FycltOXSxhcnJbTl0sYmJbTl0gOwovKgogCmxsIHNxcnR0KGxsIG4pewpsbCBse30scj0gMTAwMDAwMDAwMCsxLG1pZDsKd2hpbGUoci1sPjEpewogICAgbWlkID0gbCsoci1sKS8yOwogICAgaWYoIG1pZCAqIG1pZCA+IG4gKXI9bWlkOwogICAgZWxzZSBsID1taWQ7Cn0KcmV0dXJuIGw7Cn0KIApsbCBsY20gKCBsbCBhICwgbGwgYikKewogICAgcmV0dXJuIChhKmIpL2djZChhLGIpOwp9CiAKbGwgZmFzdF9wb3dlcihsbCBhLGxsIGIgLCBpbnQgbW9kKXsKICAgIGxsIGFucz0xOwogICAgd2hpbGUoYil7CiAgICBpZihiJjEpewogICAgICAgIGFucyo9YTsKICAgICAgICBhbnMlPW1vZDsKICAgIH0KICAgIGEqPWE7CiAgICBhJT1tb2Q7CiAgICBiID0gKGI+PjEpOwp9CnJldHVybiBhbnM7Cn0KLyoKbGwgZ2NkICggbGwgYSwgbGwgYikKewogICAgaWYgKCBiID09IDAgKQogICAgICAgIHJldHVybiBhOwogICAgcmV0dXJuIGdjZChiLCBhJWIpOwp9CnZlY3RvcjxpbnQ+IHZpcyhOKTsKdmVjdG9yPGludD4gcHJpbWUoTiApIDsKdm9pZCBnZXRfcHJpbWUoKXsKICAgIHByaW1lWzBdID0gMCAsIHByaW1lWzFdID0gMSA7CiAgICBmb3IgKGludCBpID0gMiA7IGk8PSBOIDsgaSsrKXsKICAgICAgICBpZiAoICFwcmltZVtpXSAgKXsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGkgOyBqIDw9IE4gOyBqKz1pKQogICAgICAgICAgICAgICAgcHJpbWVbal0gPSBpIDsKIAogICAgICAgIH0KICAgIH0KfQogCnZpIHByaW1zKE4pOwp2b2lkIHNlaXZlKGludCBuICl7CiAgICBwcmltc1swXSA9IHByaW1zWzFdID0gMTsKICAgIGZvciAoaW50ICBpID0gMiA7IGkqIGkgPD0gbiA7IGkrKyl7CiAgICAgICAgaWYgKCAhcHJpbXNbaV0gKXsKICAgICAgICAgICAgcHJpbXNbaV0gID0gMCA7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAyKmkgOyBqIDw9IG4gOyBqKz1pICl7CiAgICAgICAgICAgICAgICBwcmltc1tqXSA9IDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KIAp2ZWN0b3I8aW50PiBwcmltX2ZhYyhsbCBuICl7CiAgICB2ZWN0b3I8aW50PiB2OwogICAgZm9yIChpbnQgaSA9IDIgOyBpKmkgPD0gbiA7aSArKyApewogICAgICAgIHdoaWxlIChuICE9IDEgKXsKICAgICAgICAgICAgaWYgKCBuICUgaSA9PSAwICl7CiAgICAgICAgICAgICAgICBuLz1pOwogICAgICAgICAgICAgICAgdi5wdXNoX2JhY2soaSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBicmVhazsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdjsKfQogCmJvb2wgaXNfcHJpbWUoaW50IG4pCnsKICAgIGJvb2wgaXNwcmltZSA9IHRydWU7CiAgICBpZiAoIG4gPT0gMSkKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICBmb3IgKGludCBpID0gMiA7IGkgKiBpIDw9IG4gOyBpKyspCiAgICB7CiAgICAgICAgaWYgKCBuICVpID09IDAgKQogICAgICAgICAgICBpc3ByaW1lID0gZmFsc2U7CiAgICB9CiAgICByZXR1cm4gaXNwcmltZTsKfSovCiAKIAogCmNvbnN0ICBsbCBvbyA9IDFlMTgrMiAsIG1vZCA9IDFlOSs3IDsKY29uc3QgIGludCBOID0gMWU1KzU7CiAKIAogCiAKdmVjdG9yPHBhaXI8aW50LGludD4+IGFkaltOXSA7CnZlY3RvcjxpbnQ+IGRpc3QoTiwgb28pICwgYW5zICwgcGF0aChOKSAsIG1uIChOKSAsIG14KE4pIDsKIAptYXA8aW50LGludD4gbXA7CiAKbWFwPGludCwgdmVjdG9yPGludD4+IGZsaWdodHM7CiAgICAKaW50IG4gLCBtICwgayA7CiAKdm9pZCBkaWprc3RyYSggaW50IHNyYyApIHsgCiAgICBwcmlvcml0eV9xdWV1ZTwgcGlpICwgdmVjdG9yPHBpaT4gLCBncmVhdGVyPD4+IHBxOwogICAgcHEucHVzaCh7IDAsIHNyY30pOwogICAgZGlzdFtzcmNdID0gMCA7CiAgICBtblsxXSA9IDAgLCBteCBbMSBdID0gMCAsIHBhdGhbMV0gPSAxIDsKICAgIHdoaWxlICggIXBxLmVtcHR5KCkpewogICAgICAgIGludCBjdXJyID0gcHEudG9wKCkuc2Vjb25kOwogICAgICAgIGludCBkID0gcHEudG9wKCkuZmlyc3Q7CiAgICAgICAgcHEucG9wKCk7CiAgICAgICAgaWYgKCBkaXN0W2N1cnJdICE9IGQpewogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CiAgICAgICAgZm9yIChhdXRvIGl0IDogYWRqW2N1cnJdKXsKICAgICAgICAgICAgaWYgKCBkaXN0W2l0LmZpcnN0XSA+IGl0LnNlY29uZCArIGQgKXsKICAgICAgICAgICAgICAgIGRpc3RbaXQuZmlyc3RdID0gaXQuc2Vjb25kICsgZCA7CiAgICAgICAgICAgICAgICBwcS5wdXNoKHtkaXN0W2l0LmZpcnN0XSAsIGl0LmZpcnN0fSk7CiAgICAgICAgICAgICAgICBwYXRoW2l0LmZpcnN0XSA9IHBhdGhbY3Vycl07CiAgICAgICAgICAgICAgICBtbltpdC5maXJzdF0gPSBtbltjdXJyXSsxOwogICAgICAgICAgICAgICAgbXhbaXQuZmlyc3RdID0gbXhbY3Vycl0gKyAxIDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmICggZGlzdFtpdC5maXJzdF0gPT0gaXQuc2Vjb25kICsgZCApewogICAgICAgICAgICAgICAgcGF0aFtpdC5maXJzdF0gPSAoIHBhdGhbaXQuZmlyc3RdICUgbW9kICsgcGF0aFtjdXJyXSVtb2QgICkgJSBtb2QgOwogICAgICAgICAgICAgICAgbW5baXQuZmlyc3RdID0gbWluICggbW5baXQuZmlyc3RdICwgbW5bY3Vycl0gKzEgKTsKICAgICAgICAgICAgICAgIG14W2l0LmZpcnN0XSA9IG1heCAoIG14W2l0LmZpcnN0XSAsIG14W2N1cnJdICsxICk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAKfQogCiAKdm9pZCBzb2x2ZSggKXsKICAgIGNpbiA+PiBuID4+IG0gIDsKICAgIHdoaWxlICggbSAtLSApewogICAgICAgIGludCBhICwgYiAsIHcgOwogICAgICAgIGNpbiA+PiBhICA+PiAgYiA+PiB3IDsKICAgICAgICBhZGpbYV0ucHVzaF9iYWNrKHtiLHcgfSk7CiAgICB9CiAgICBkaWprc3RyYSgxKTsKICAgIGNvdXQgPDwgZGlzdFtuXSA8PCAnICcgPDwgcGF0aFtuXSA8PCAnICcgPDwgbW5bbl0gPDwnICc8PCBteFtuXSA8PCBlbmRsOwogICAgIAogICAgCn0KIApzaWduZWQgbWFpbiggKQp7CiAgICAvLyAgIGZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKTsKICAgIC8vICBmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKLy8jZW5kaWYKICAgIGZhc3QoKTsKICAgIGludCB0ID0xOwogICAgY2xvY2tfdCB3ID1jbG9jaygpOwogICAgLy8gY2luID4+IHQgOwogICAgd2hpbGUgKCB0IC0tICl7CiAgICAgICAgc29sdmUoKTsKICAgIH0KICAgICAgICAKLy8gY2VyciA8PCAiUnVuIHRpbWUgOiAiIDw8ICgoZG91YmxlKSAoY2xvY2soKSAtIHcpIC8gQ0xPQ0tTX1BFUl9TRUMpOwp9