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

using namespace std;

struct edge
{
    int nod,c;
};

struct elem
{
    int nod,c;
};

struct cmp
{
    bool operator()(const elem &e1,const elem &e2)
    {
        return e1.c>e2.c;
    }
};

priority_queue<elem, vector<elem> , cmp> Q;
vector<edge> graph[50001];
int cost[50001],n,m;

void expand()
{
    elem el=Q.top();
    if(cost[el.nod]>el.c||cost[e1.nod]==0)
    {
        cost[el.nod]=el.c;
        for(int i=0;i<graph[el.nod].size();++i)
        {
            edge e=graph[el.nod][i];
            elem e2;e2.nod=e.nod;e2.c=el.c+e.c;
            Q.push(e2);
        }
    }
    Q.pop();
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    //for(int i=1;i<=n;++i)cost[i]=999999999;
    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        edge e;e.c=c;e.nod=y;
        graph[x].push_back(e);
    }

    elem e;e.nod=1;e.c=0;
    Q.push(e);
    while(Q.size()>0)expand();
    for(int i=2;i<=n;++i)printf("%d ",cost[i]);
    return 0;
}