#include <fstream>

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int INF = 999999;

int n,src;
int cost[750][750];
int dist[50005];
int parent[50005], visited[50005];

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;

    return minnode;
}


void dijkstra(){
    int i,nearest,j;
    for(j=1;j<=n;j++){
    nearest = getNearest();
    visited[nearest]=1;
    for(i=1;i<=n;i++)
        if(nearest!=-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(){

    int i,p;
    for(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;

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(cost[i][j]==-1)
            cost[i][j]=0;

    src = 1;
    init();
    dijkstra();
    print();
    return 0;
}