#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define mod 1000000007
#define mod2 998244353
#define pb push_back
#define ll long long
#define fi first
#define lb lower_bound
#define test ll int t;cin>>t;while(t--)
#define se second
#define pll pair<long long,long long>
#define icc ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
  
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  
ll gcd(ll a, ll b){
    if(!a)return b;
    return gcd(b%a,a);
}
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a);}
                a=(a*a);
                b>>=1;
        }
    return ans;
}
vector<ll> spf,prime;
void primes(ll n){
    spf.assign(n+1,0);
    spf[1] = 1;
    for(ll i=2; i<=n; i++){
        if (!spf[i]){
         spf[i]=i;prime.pb(i);
         for (ll j=i*i; j<=n; j+=i)
         if (!spf[j])
         spf[j] = i;
        }
    }
}
ll fact[1000001];
void factorial(ll n){
	fact[0]=1;
	for(ll i=1;i<=n;i++){
		fact[i]=fact[i-1]*i;
		if(fact[i]>=mod)
			fact[i]%=mod;
	}
}
priority_queue<ll,vector<ll>,greater<ll> > qqqqq;

void solve(){
   ll a,b,c,d;
   cin>>a>>b>>c>>d;
   if(c*d-b<0){cout<<"-1";return;}
   for(ll i=0;i<10000000;i++){
       if(a<=(c*d-b)*i){
           cout<<i;
           return ;
       }
   }
   cout<<"-1";
}
int main(){
    icc;
    //test
    solve();
	return 0;
}
// ll op;
// 	cin>>op;
// 	for(ll fff=1;fff<=op;fff++){
        
// 		cout<<"Case #"<<fff<<": "<<ans<<endl;
// 	}

//#include <atcoder/maxflow.hpp>
#include <memory>
#include <iostream>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>
#include <complex>
#include <thread>
#include <bitset>

#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

using namespace std;
//using namespace atcoder;

//ll modd = (1000LL * 1000LL * 1000LL + 7LL);
ll modd = 998244353;

ll binary_search(function<bool(ll)> func, ll start, ll end) {
    /*      func:int ->bool
            returns smallest int x where func(x) evaluates to true, searches in [start,end), it is assumed the values are false, .. , false, true ...
             */
    if (end <= start) {   return end;  }   // has to be here, otherwise func(end-1) in next line could be a problem
    if (!func(end-1)) {  return end;  }
    while (end-start>1) {
        ll mid = (start+end)/2;
        if (func(mid)) {  end = mid;  } else { start = mid;   }
    }
    if (func(start)) {  return start;  } else {  return end;   }
};


int main(int argc, char *argv[])   {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout.precision(17);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no

//    auto start = chrono::steady_clock::now();


//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readint(n); readint(m);
        vector<vector<pair<int,ll>>> adj(n);
        forr(i,0,m) {
            readint(aa); readint(bb); readll(cc); --aa; --bb;
            adj[aa].push_back(make_pair(bb,cc));
        }

        vector<vector<ll>> dist;
        forr(i,0,n) {
            priority_queue<pair<ll,int>> todo;
            for(auto nn : adj[i]) {
                todo.push(make_pair(-nn.second, nn.first));
            }
            dist.push_back(vector<ll>(n, modd*modd));
            while (!todo.empty()) {
                auto curr = todo.top(); todo.pop();
                if (-curr.first < dist.back()[curr.second]) {
                    dist.back()[curr.second] = -curr.first;
                    for(auto nn : adj[curr.second]) {
                        todo.push(make_pair(-nn.second+curr.first, nn.first));
                    }
                }
            }
            cout << ((dist.back()[i] == modd*modd) ? -1 : dist.back()[i]) << endl;
        }


    }

//        auto stop = chrono::steady_clock::now(); 
//        auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start);
//        cout << "Duration: " << duration.count() << endl;
    return 0;
}



