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

#define INF 2000000000

using namespace std;

int n,m,d[50001];

struct graf
{
    int x,val;
};

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

priority_queue <int , vector<int>, cmp> q;
vector <graf> G[50001];

void dijkstra()
{
    int i,k,nod;

    q.push(1);
    while(!q.empty())
    {
        nod=q.top();
        q.pop();

        int k=G[nod].size();
        for(i=0; i<k; i++)
        {
            if(d[G[nod][i].x]>d[nod]+G[nod][i].val)
            {
                d[G[nod][i].x]=d[nod]+G[nod][i].val;
                q.push(G[nod][i].x);
            }
        }
    }
}

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

    int i;

    scanf("%d %d",&n,&m);

    for(i=1; i<=m; i++)
    {
        int x;
        graf aux;
        scanf("%d %d %d",&x,&aux.x,&aux.val);
        G[x].push_back(aux);
    }
    for(i=2; i<=n; i++) d[i]=INF;

    dijkstra();

    for(i=2; i<=n; i++)
    {
        if(d[i]<INF) printf("%d ",d[i]);
        else printf("0 ");
    }


}