#include <iostream>
#include <fstream>
#include <list>

using namespace std;

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

const int inf=1<<30;

list <int> adj[55555];
list <int> cost[55555];
int n,m;
int dist[55555];
bool viz[55555];

int distmin()
{
    int k=50505;
    dist[k]=inf;
    for(int i=1;i<=n;++i)
        if(dist[i]<dist[k] and !viz[i])
            k=i;
    return k;
}

void dijkstra()
{
    for(int i=1;i<=n;++i)
        dist[i]=inf;
    dist[1]=0;
    for(int i=1;i<=n-1;++i)
    {
        int nc=distmin();
        viz[nc]=1;
        list <int> :: iterator it,jt;
        for(it=adj[nc].begin(),jt=cost[nc].begin();it!=adj[nc].end();++it,++jt)
        {
            int v=*it;
            int cat=*jt;
            if(dist[v]>dist[nc]+cat)
                dist[v]=dist[nc]+cat;
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b,c;
        f>>a>>b>>c;
        adj[a].push_back(b);
        cost[a].push_back(c);
    }
    dijkstra();
    for(int i=2;i<=n;++i)
        g<<dist[i]<<' ';
    return 0;
}