#include<queue>
#include<iostream>
#include<fstream>
#include<limits.h>
#include<vector>

#define FOR(a,b,c) for(a=b;a<=c;a++)
#define Nmax 50010
#define MAX 99999
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


struct arc{
    int weight;
    bool connected;
};
arc **cost;
int N, M;
int i,j;
int x,y,w;
int *dist;

class compare{
public:
       bool operator()(const int &a, const int &b) const
    {
        return dist[a]<dist[b];
    }
};
void Dijkstra()
{
    priority_queue <int, vector<int>, compare > Q;
    int k;

    FOR(i,1,N)
        {
            dist[i] = MAX;

            Q.push(i);
        }


        dist[1]=0;
        while(!Q.empty())
        {

            int u = Q.top();

            Q.pop();

            FOR(k,2,N)
            if(cost[u][k].connected)
                if(dist[k] > dist[u] + cost[u][k].weight && u!=k )
                {
                    dist[k] = dist[u] + cost[u][k].weight;

                }

        }

}

int main()
{
    f>>N>>M;

    cost = new arc*[N+1];
    FOR(i,1,N)
        cost[i] = new arc[N+1];

    FOR(i,1,N)
        FOR(j,1,N){
            cost[i][j].weight=0;
            cost[i][j].connected=false;
        }



    dist = new int[N+1];
    FOR(i,1,M)
         {
             f>>x>>y>>w;
             cost[x][y].weight=w;
             cost[x][y].connected=true;
         }
    FOR(i,1,N)
    {
        FOR(j,1,N)
        {
          cout<<cost[i][j].weight<<","<<cost[i][j].connected<<" | ";
        }
        cout<<endl;
    }

    Dijkstra();

    FOR(i,2,N)
    if(dist[i]== MAX)
        g<<0<<" ";
    else
        g<<dist[i]<<" ";

    return 0;
}