#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50010
#define INF (1<<30)
#define PII pair < int , int >
#define PMP(x,y) push(make_pair(x,y))
#define PBMP(x,y) push_back(make_pair(x,y))
#define Gedge first
#define Gcost second
#define PQedge second

int N,M;
int Dist[NMAX];         //The distances array

bool Used[NMAX];        //The already-visited-edge array

vector < PII > G[NMAX];     //The vector with all the adjacent edges and their costs
                            //(first = the edge, second = the cost)

priority_queue < PII , vector < PII > , greater < PII > > PQ;       //The priority queue from which we extract the edges for the Dijkstra algorithm
                                                                    //PQ.top() = the lowest value of the PQ
                                                                    //(first = the distance, second = the edge)

void Read()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&N,&M);
    for(int i=1,x,y,z;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].PBMP(y,z);
    }
}

void Solve_Dijkstra()
{
    //Initialise the distances array
    for(int i=2;i<=N;Dist[i++]=INF);
    //Add the first edge to the PQ
    PQ.PMP(0,1);

    while(!PQ.empty())
    {
        //We extract the lowest value from the PQ
        //and update the edges adjacent with it
        int edge = PQ.top().PQedge;
        PQ.pop();

        if(Used[edge])
            continue;
        Used[edge] = true;

        for(vector < PII > :: iterator it = G[edge].begin(); it!= G[edge].end();++it)
            if(Dist[(*it).Gedge] > Dist[edge] + (*it).Gcost)
            {
                Dist[(*it).Gedge] = Dist[edge] + (*it).Gcost;
                PQ.PMP(Dist[(*it).Gedge],(*it).Gedge);
            }
    }
}

void Print()
{
    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=N;i++)
        (Dist[i]!=INF)?(printf("%d ",Dist[i])):(printf("0 "));
}

int main()
{
    Read();
    Solve_Dijkstra();
    Print();
    return 0;
}