# include<bits/stdc++.h>

using namespace std;
# define l long long 
# define db double 
# define rep(i,a,b) for(l i=a;i<b;i++)
# define vi vector<l>
# define vvi vector<vi>
# define vsi vector<set<l> >
# define pb push_back
# define mp make_pair
# define ss second
# define ff first
# define pii pair<l,l>
# define trvi(v,it) for(vi::iterator it=v.begin();it!=v.end();++it)
# define read(a) freopen(a,"r",stdin)
# define write(a) freopen(a,"w",stdout)
# define io ios::sync_with_stdio(false)

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ' ' << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 

#ifdef KRISHNAN_DEBUG
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const bool MULTIPLE_TEST_CASES = false;

const l MOD=1e9+7;
const l N=1e5+5;
const l INF=1e12;

l H,W,A,B;

void cnt(vector<vector<bool> > &visited, l A_rem, l B_rem, l &ans) {
	if(A_rem<0 || B_rem<0) {
		return;
	}
	if(A_rem==0 && B_rem==0) {
		ans++;
		return;
	
	}
	bool found = false;
	l i=-1,j=-1;
	for(l x=0;x<H;x++) {
		
		for(l y=0;y<W;y++) {
			if(visited[x][y]==false) {
				i=x;
				j=y;
				found = true;
				break;
			}
		}
		if(found) {
			break;
		}
	}
	if(i==-1 || j==-1) {
		return;
	}
	dbg(i,j);
	visited[i][j]=true;
	cnt(visited, A_rem, B_rem-1,ans);

	if(i+1<H && visited[i+1][j]==false) {
		visited[i+1][j]=true;
		cnt(visited, A_rem-1, B_rem,ans);
		visited[i+1][j]=false;
	}

	if(j+1<W && visited[i][j+1]==false) {
		visited[i][j+1]=true;
		cnt(visited, A_rem-1, B_rem,ans);
		visited[i][j+1]=false;
	}
	visited[i][j] = false;
}

void solve() {
	
	cin>>H>>W>>A>>B;

	vector<vector<bool> > visited(H, vector<bool>(W, false));

	l ans = 0;
	cnt(visited, A, B, ans);
	cout<<ans<<"\n";

	return;
}


int main(){
	io;
	int t=1;
	if (MULTIPLE_TEST_CASES) cin>>t;
	rep(i,0,t) {
		solve();
	}

	return 0;
}

#include <bits/stdc++.h>
/* #include <atcoder/all> */

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;
/* using namespace atcoder; */

using ll = long long;
using P = pair<int, int>;

const ll INF = 1 << 30;

template<class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

struct Data {
  int to;
  ll cost;
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> dist(n, INF);
  vector<vector<ll>> G2(n, vector<ll>(n, INF));
  vector<vector<Data>> G(n, vector<Data>());
  rep(i, m) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--;
    b--;
    if (a == b) {
      chmin(dist.at(a), c);
    } else {
//      chmin(G2.at(a).at(b), c);
      Data d = {b, c};
      G.at(a).push_back(d);
    }
  }
//  vector<vector<Data>> G(n, vector<Data>());
  rep(i, n) {
    rep(j, n) {
      if (i == j) continue;
    }
  }

  vector<vector<ll>> dist2(n, vector<ll>(n, INF));
  rep(i, n) {
    vector<ll> dist3(n, INF);
    dist3.at(i) = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>,
        greater<pair<ll, int>>> que;
    que.push(make_pair(dist3.at(i), i));
    while (!que.empty()) {
      int v = que.top().second;
      ll d = que.top().first;
      que.pop();
      if (d > dist3.at(v)) continue;
      for (auto e : G.at(v)) {
        if (e.to == i) {
          continue;
        }
        if (chmin(dist3.at(e.to), dist3.at(v) + e.cost)) {
          que.push(make_pair(dist3.at(e.to), e.to));
        }
      }
    }
    rep(j, n) {
//      cerr << dist3.at(j) << " ";
      dist2.at(i).at(j) = dist3.at(j);
    }
//    cerr << endl;
  }
  rep(i, n) {
    rep(j, n) {
      if (i == j) continue;
      dist.at(i) = min(dist.at(i), dist2.at(i).at(j) + dist2.at(j).at(i));
    }
  }
  rep(i, n) {
    cout << ((dist.at(i) == INF) ? -1 : dist.at(i)) << endl;
  }
  return 0;
}
