#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define inf 5000000000

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod{
    int u,c;
}aux;

vector <nod>   G[50000];
vector <int> v;
queue <int> q;

void dijkstra(int front)
{
    int fr;
    v[front]=0;
    q.push(front);
    while( !q.empty() )
    {
        fr=q.front();
        for(int i=0;i<G[fr].size(); i++)
            if ( v[G[fr][i].u]>v[fr]+G[fr][i].c)
            {
                v[G[fr][i].u]=v[fr]+G[fr][i].c;
                q.push(G[fr][i].u);
            }
        q.pop();
    }
}


int main()
{
    int n,m,a,b,c;
    f>>n>>m;

    v.resize (n+1,inf);
    for(;m;--m)
    {
        f>>a>>b>>c;
        aux.u=b;
        aux.c=c;
        G[a].push_back(aux);
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        g<<v[i]<<" ";
    return 0;
}