#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+500;
ll inf=1e18;

int gti(void)
{
	char c=getchar();
	int ret=0,st=1;
	for (;c!='-'&&!isdigit(c);c=getchar());
	if (c=='-') st=-1,c=getchar();
	for (;isdigit(c);c=getchar()) ret=ret*10+c-'0';
	return ret*st;
}

struct edge{edge *nxt;int to;ll len;}pool[N],*pt[N],*p=pool;
void addedge(int a,int b,int l)
{
	*(++p)=(edge){pt[a],b,l},pt[a]=p;
}

struct P
{
	int id;
	ll dis;
	bool operator<(const P &b)const
	{
		return dis>b.dis;
	}
};
priority_queue<P> hp;
ll dis[N];
void dijkstra(int v,int n)
{
	for (int i=1;i<=n;i++) dis[i]=inf;
	for (edge *i=pt[v];i;i=i->nxt)
	{
		dis[i->to]=min(dis[i->to],i->len);
		hp.push((P){i->to,dis[i->to]});
	}
	P now;
	for (int i=1;i<=n*2;i++)
	{
		if (hp.size()==0) break;
		for (now=hp.top(),hp.pop();hp.size()&&dis[now.id]!=now.dis;)
			now=hp.top(),hp.pop();
		if (dis[now.id]!=now.dis) break;
		for (edge *i=pt[now.id];i;i=i->nxt)
			if (dis[i->to]>dis[now.id]+i->len)
			{
				dis[i->to]=dis[now.id]+i->len;
				hp.push((P){i->to,dis[i->to]});
			}
	}
	if (dis[v]>=inf) puts("-1");
	else printf("%lld\n",dis[v]);
}

int main(void)
{
	int n=gti(),m=gti();
	for (int i=1;i<=m;i++)
	{
		int u=gti(),v=gti(),w=gti();
		addedge(u,v,w);
	}
	for (int i=1;i<=n;i++)
		dijkstra(i,n);
	return 0;
}

#pragma region Region_1

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (ll i = s; i < t; ++i)
#define rng(a) a.begiGn(), a.end()
#define rrng(a) a.rbegin(), a.rend()
using ll = long long;
using P = pair<ll, ll>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VP = vector<P>;
using VS = vector<string>;
using VC = vector<char>;
using VVC = vector<vector<char>>;
#define MOD 1000000007
// #define MOD 998244353
const int INF = (int)1e9 + 10;         // int max > 2*10^9
const long long INFL = (ll)2e18 + 10;  // ll max > 9*10^18

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

template <class T>
T sum(const vector<T>& v) {
    T res = 0;
    for (size_t i = 0; i < v.size(); ++i) res += v[i];
    return res;
}

/////////////////////////////////////////////////////////
// print like python
// https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed
/////////////////////////////////////////////////////////
void print() { cout << endl; }

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << " ";
    print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T>& vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << " ";
    }
    cout << endl;
}

template <class T>
void print(vector<vector<T>>& df) {
    for (auto& vec : df) {
        print(vec);
    }
}

#pragma endregion Region_1
/////////////////////////////////////////////////////////
struct mint {
    ll x;  // typedef long long ll;
    int mod;
    mint(ll x = 0, int mod = MOD) : x((x % mod + mod) % mod), mod(mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    // x^t
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;  // 桁ずらし
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
using VMI = vector<mint>;
using VVMI = vector<vector<mint>>;

mint calc_cmb(int n, int m) {
    if (n - m < m) m = n - m;
    mint x = 1;
    mint d = 1;
    for (int i = 0; i < m; ++i) {
        x *= (n - i);
        d *= (i + 1);
    }
    return x / d;
}
int main() {
    std::cout << std::setprecision(15);
    //////////////////////////////////////////
    ll n, m, k;
    cin >> n >> m >> k;
    if (n > m + k) {
        print(0);
        return 0;
    }

    mint a = calc_cmb((n + m), m);
    mint b = calc_cmb((n + m), m + k + 1);
    if (k + 1 > n) b = mint(0);

    print((a - b).x);

    return 0;
}