#include <iostream>
#include <fstream>

using namespace std;

struct graf
{
    int x,y,cost;
};

void Bellman_Ford(graf graph[], int noduri, int muchii, int start)
{
    int dist[noduri];
    for(int i=0;i<noduri;i++)
        dist[i]=9999999;
    dist[start]=0;
    for(int i=0;i<noduri-1;i++)
        for(int j=0;j<muchii;j++)
            if(dist[graph[j].y]>dist[graph[j].x]+graph[j].cost)
                dist[graph[j].y]=dist[graph[j].x]+graph[j].cost;
    for(int i=0;i<noduri;i++)
        cout<<i<<"->"<<dist[i]<<"\n";
}


int main()
{
    int noduri,muchii,i,j;
    ifstream fin("bell.in");
    fin>>noduri>>muchii;
    graf g[muchii+1];
    for(i=0;i<muchii;i++)
        fin>>g[i].x>>g[i].y>>g[i].cost;
    Bellman_Ford(g,noduri,muchii,0);
    return 0;
}