#include <bits/stdc++.h> 
#include <math.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vpl = vector<pair<ll, ll>>;
using pll = pair<ll, ll>;
#define rep(i, k, n) for(ll i = k; i < n; i++)
#define pb push_back
#define mp make_pair

ll n, m, s; //頂点の数, 辺の数, スタート地点
vll A(3010);  //辺の始点
vll B(3010);  //辺の終点
vll C(3010);  //辺のコスト
vll dist(3010);   //最短距離
vector<vpl> G(3010, vpl(0));  //隣接する頂点とコストをセットにした記憶したもの
priority_queue<pll, vpl, greater<pll>> Q;

int main(){
    cin >> n >> m;
    rep(i, 1, m+1){
        cin >> A[i] >> B[i] >> C[i];
        G[A[i]].pb(mp(C[i], B[i]));
    }

    rep(i, 1, n+1){
        //距離の初期化
        rep(j, 0, 3010){
            dist[j] = 1000000007;
        }

        //帰ってくる場所の追加
        rep(j, 1, n+1){
            rep(k, 0, G[j].size()){
                if(G[j][k].second == i){
                    G[j].pb(mp(G[j][k].first, 3000));
                }
            }
        }

        //優先度付きキューに(距離, 頂点番号)の組を入れる
        Q.push(mp(0, i));
        dist[i] = 0;

        while(!Q.empty()){
            ll pos = Q.top().second;
            Q.pop();
            rep(j, 0, G[pos].size()){
                ll to = G[pos][j].second;
                ll cost = G[pos][j].first;
                //posを経由してtoに行く距離がdist[to]より短ければ
                //dist[to]を更新してキューに入れる
                if(dist[to] > dist[pos] + cost){
                    dist[to] = dist[pos] + cost;
                    Q.push(mp(dist[to], to));
                }
            }
        }

        //帰ってくる場所の削除
        rep(j, 1, n+1){
            ll rec = 0;
            rep(k, 0, G[j].size()){
                if(G[j][k].second == 3000){
                    rec++;
                }
            }

            rep(k, 0, rec){
                G[j].pop_back();
            }
        }

        // cout << i << " : ";
        // rep(j, 0, 3010){
        //     if(dist[j] != 1000000007){
        //         cout << "{" << j << ", " << dist[j] << "}";
        //     }
        // }

        if(dist[3000] != 1000000007){
            cout << dist[3000] << endl;
        }
        else{
            cout << -1 << endl;
        }

    }

    // rep(i, 1, n+1){
    //     cout << i << " : ";
    //     rep(j, 0, G[i].size()){
    //         printf(" {%lld, %lld},", G[i][j].second, G[i][j].first);
    //     }
    //     cout << endl;
    // }

    

}   
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <limits.h>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 110;
int H, W, A, B, ans = 0;
void solve(int s, int bit, int a, int b)
{
	if(s==H*W)
	{
		ans++;
		return ;
	}
	if(bit&(1<<s)) return solve(s+1, bit, a, b);
	if(a)
	{
		if(s%W!=W-1 && !(bit&(1<<(s+1)))) solve(s+1, bit|(1<<s)|(1<<(s+1)), a-1, b);
		if(s+W<H*W) solve(s+1, bit|(1<<s)|(1<<(s+W)), a-1, b);
	}
	if(b) solve(s+1, bit|(1<<s), a, b-1);
}
int main()
{
	//freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
	cin >> H >> W >> A >> B;
	solve(0, 0, A, B);
	cout << ans << endl;
	return 0;
}
