#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

const int Infinit = 0x3f3f3f;
const int N = 50002;

struct lol
{
    int inf,c;
};

vector <lol> V[N];
int cost[N],n,m,viz[N];

struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        return cost[a]>cost[b];
    }
};

priority_queue <int ,vector<int> , cmp> Q;

void citire()
{
    int a;
    lol x;
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d %d",&a,&x.inf,&x.c);
        V[a].push_back(x);
    }
}

void dijkstra()
{
    for (int i=2;i<=n;i++)
        cost[i]=Infinit;
    viz[1]=1;
    Q.push(1);
    int top,topC,top2;
    while (!Q.empty())
    {
        top=Q.top();
        Q.pop();
        topC=cost[top];
        viz[top]=0;
        for (int i=0;i<V[top].size();i++)
        {
            top2=V[top][i].inf;
            if (cost[top2] > topC + V[top][i].c)
            {
                cost[top2] = topC + V[top][i].c;
                if (!viz[top2])
                {
                    viz[top2]=1;
                    Q.push(top2);
                }
            }
        }
    }

    for (int i=2;i<=n;i++)
        printf("%d ",cost[i]==Infinit?0:cost[i]);
}

int main ()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    return 0;
}