spoj

   #include<bits/stdc++.h>
using namespace std;
const long inf = numeric_limits<long>::max();
void shortest(vector<pair<int,pair<int,int> > >&v,int n,int m,int p)
{ vector<long>dist(n,inf);
    vector<int>vp(n,0);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {  dist[p]=0;
            int x=v[j].first;
            int y=v[j].second.first;
            int z=v[j].second.second;
            if(dist[x]!=inf && dist[y]>(dist[x]+z))
            {dist[y]=dist[x]+z;
            if(i==n-1) vp[y]=1;}
        }
    }
    for(int i=0;i<n;i++)
   {
        if(i==p) cout<<"0"<<endl;
       else if(vp[i]==1) cout<<"-"<<endl;
        else if(dist[i]==inf) cout<<"*"<<endl;

        else cout<<dist[i]<<endl;
    }
}

int main()
{
    int n,m,p;
    cin>>n>>m;
    vector<pair<int,pair<int,int> > >v;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--;y--;
        v.push_back(make_pair(x,make_pair(y,z)));
    }
    cin>>p; p--;
    shortest(v,n,m,p);
}