#include <fstream>

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int INF = 9999999;

long long n,src;
long long cost[50002][50002];
long long dist[500005];
long long parent[500005], visited[500005];

void init(){
    int i;
    for(i=1;i<=n;i++)
        {
          dist[i]=INF;
          parent[i]=i;
        }

    dist[src] = 0;
}

int getNearest(){
    int minvalue,minnode,i;
    minvalue = INF;
    minnode = -1;
    for(i=1;i<=n;i++)
        if(dist[i] < minvalue && visited[i] == 0)
            {
                minnode = i;
                minvalue = dist[i];
            }

    return minnode;
}


void dijkstra(){
    int i,nearest,j,l;
    for(j=1;j<=n;j++){
    nearest = getNearest();
    visited[nearest]=1;

    for(i=1;i<=n;i++)
        if(minnode!=-1)
        if(cost[nearest][i]!=INF && dist[i]> cost[nearest][i] + dist[nearest])
            {
            dist[i] = cost[nearest][i] + dist[nearest];
            parent[i] = nearest;
            }
        }
}

void print(){
    for(int i=2;i<=n;i++)
        if(dist[i]!=INF)
            cout<<dist[i]<<" ";
        else
            cout<<0<<" ";
}

int main()
{
    int i,j,m;
    int a,b,c;
    cin>>n>>m;
    for(i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            if(c!=0)
                cost[a][b] = c;
            else
                cost[a][b] = -1;
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(cost[i][j]==0 && i!=j)
            cost[i][j]=INF;
        else
            if(cost[i][j]==-1)
                cost[i][j]=0;
    src = 1;
    init();
    dijkstra();
    print();
    return 0;
}