#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");

int **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);
        }

        /*while(!Q.empty())
        { cout<<Q.top()<<endl;Q.pop(); }*/

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

            int u = Q.top();

            Q.pop();

            FOR(k,2,N)

                if(dist[k] > dist[u] + cost[u][k] && u!=k && cost[u][k]!=0)
                {
                    dist[k] = dist[u] + cost[u][k];

                }

        }

}

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

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

    FOR(i,1,N)
        FOR(j,1,N)
            cost[i][j]=0;


    dist = new int[N+1];
    FOR(i,1,M)
         {
             f>>x>>y>>w;
             cost[x][y]=w;
         }

    Dijkstra();

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