#include <fstream>
#include <queue>

using namespace std;

#define inf 9000

int N,M;
int graph[5000][5000];
int dist[5000];
int parent[5000];
bool selectat[5000];

void dijkstra(int sursa)
{

    queue<int> qu;

    int i,cnode;
    for(i = 1; i <= N; i++)
    if(graph[sursa][i] != inf)
    {
        dist[i] = graph[sursa][i];
        parent[i] = sursa;
        qu.push(i);
        selectat[i] = true;
    }

    //Relaxeaza
    while(!qu.empty())
    {
        cnode = qu.front();
        qu.pop();

        //Vecinii
        for(i = 1; i <= N; i++)
        {
            if(selectat[i] == false && dist[i] > dist[cnode] + graph[cnode][i]){
                dist[i] = dist[cnode] + graph[cnode][i];
                parent[i] = cnode;
            }
        }
    }
}


int main(){

    int i,j,cost,x,y;

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

    in >> N >> M;

    for(i = 1; i <= N; i++)
    for(j = 1; j <= N; j++)
    {
        graph[i][j] = inf;
    }

    for(i = 1; i <= N; i++){
        in >> x >> y >> cost;
        graph[x][y] = cost;

        dist[i] = inf;
    }

    dijkstra(1);

    for(i = 2; i <= N; i++)
        out << dist[i] << " ";

    in.close();
    out.close();

    return 0;
}